ඩී දින ලීට්කෝඩ් විසඳුම තුළ පැකේජ නැව්ගත කිරීමේ හැකියාව


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන්
අරා ද්විමය සෙවීම

ගැටළු ප්රකාශය

“දින කිහිපයක් ඇතුළත පැකේජ නැව්ගත කිරීමේ හැකියාව” යන ගැටලුවේදී, අපට වරාය A හි පැකට් තිබේ, ඒවා D දිනවලදී B වරායට මාරු කළ යුතුය.

එක් එක් පැකට්ටුවක බර සහ පැකට් මාරු කළ යුතු දින ගණන අඩංගු බර අරාවක් අපට ලබා දී ඇත. අපගේ කාර්යය වන්නේ ඩී දිනවලදී A වරායේ සිට B වරායට පැකට් මාරු කිරීම සඳහා භාවිතා කළ යුතු අවම බර ධාරිතාව සොයා ගැනීමයි.

ඩී දින තුළ පැකේජ නැව්ගත කිරීමේ ධාරිතාවට ලීට්කෝඩ් විසඳුම

උදාහරණයක්

weights = [1,2,3,4,5,6,7,8,9,10], D = 5
15

පැහැදිලි කිරීම: නැව පහත පරිදි පැකට් මාරු කරනු ඇත:

පළමු දිනය: 1,2,3,4,5

දෙවන දිනය 2: 6,7

තෙවන දිනය 3: 8

හතරවන දිනය 4: 9

පස්වන දිනය 5: 10

මේ ආකාරයට, දින 15 ක් තුළ සියලුම පැකට් මාරු කිරීම සඳහා නැවේ අවම බර ධාරිතාව 5 ක් විය යුතුය.

ඩී දින ලීට්කෝඩ් විසඳුම තුළ පැකේජ නැව්ගත කිරීමේ හැකියාව සඳහා ප්‍රවේශය

මෙම ගැටළුව විසඳීම සඳහා පළමු හා වැදගත්ම දෙය වන්නේ නිරීක්ෂණ ගෙන ඒමයි. අපගේ සෙවුම් කාල පරතරය සඳහා නිරීක්ෂණ කිහිපයක් මෙන්න:

  1. නැවේ බර පැටවීමේ ධාරිතාව උපරිම (බර) උපරිම බර ඇති පැකට්ටුවට අවම වශයෙන් සමාන විය යුතුය. අපි එය නම් කරමු ආරම්භයක්.
  2. නෞකාවේ උපරිම ධාරිතාවය සියලු පැකට් වල බර (බර) දක්වා සීමා කළ හැකිය. අපි එය නම් කරමු අවසානය.

දැන් අපට අපගේ සෙවුම් පරතරය ඇත. පරතරයේ ප්‍රමාණය යැයි සිතමු දිග පැකට් ගණන වේ n.  අශෝභන ප්‍රවේශය වනුයේ එම බර ධාරිතාව ඩී දින තුළ සාර්ථකව පැකට් මාරු කර ඒවායින් අවම ප්‍රමාණයක් තෝරා ගත හැකි නම්, එක් එක් අගය පරතරය පරීක්ෂා කිරීමයි. බොළඳ ප්‍රවේශය සඳහා කාල සංකීර්ණත්වය දිග * n වේ.

රේඛීය සෙවීම වෙනුවට ද්විමය සෙවුම භාවිතා කිරීමෙන් අපට කාල සංකීර්ණතාව වැඩි දියුණු කළ හැකිය.

භාවිතා කරන කාල සංකීර්ණත්වය ද්විමය සෙවීම ප්‍රවේශය ලොග් වනු ඇත (දිග) * n.

ක්රියාත්මක කිරීම

ඩී දින ලීට්කෝඩ් විසඳුම තුළ පැකේජ නැව්ගත කිරීමේ ධාරිතාව සඳහා සී ++ කේතය

#include <bits/stdc++.h>
using namespace std; 
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4,5,6,7,8,9,10}; 
 int d=5;                               

 cout<<shipWithinDays(arr,d)<<endl;
 return 0;
}
15

ඩී දින ලීට්කෝඩ් විසඳුම තුළ පැකේජ නැව්ගත කිරීමේ හැකියාව සඳහා ජාවා කේතය

public class Tutorialcup {
    public static int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5,6,7,8,9,10}; 
     int d=5; 
    int ans= shipWithinDays(arr,d);
    System.out.println(ans);
  }
}
15

ඩී දින ලීට්කෝඩ් විසඳුම තුළ පැකේජ නැව්ගත කිරීමේ හැකියාව පිළිබඳ සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඉහත කේතයේ කාල සංකීර්ණතාව වේ O (n * log (දිග)) මොකද අපි බර අරා ලොග් (දිග) වාර ගණනක් ගමන් කරනවා. මෙහි n සහ දිග යනු පිළිවෙලින් පැකට් ගණන සහ සෙවුම් පරතරයේ ප්‍රමාණයයි.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ ඕ (1) පිළිතුර භාවිතා කිරීමට අප භාවිතා කරන්නේ විචල්‍යය පමණි.

ආශ්රිත