ડી ડેટ્સ લિટકોડ સોલ્યુશનમાં પેકેજો શિપ કરવાની ક્ષમતા


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન
અરે દ્વિસંગી શોધ

સમસ્યા નિવેદન

"ડી દિવસમાં પેકેજો શિપ કરવા માટેની ક્ષમતા," સમસ્યામાં, અમારી પાસે બંદર એમાં પેકેટો છે જે ડી દિવસોમાં બંદર બીમાં સ્થાનાંતરિત થવું આવશ્યક છે.

અમને વેઇટ એરે આપવામાં આવે છે જેમાં દરેક પેકેટનું વજન અને પેકેટ્સને સ્થાનાંતરિત કરવાની જરૂરિયાતની સંખ્યા છે. અમારું કાર્ય એ છે કે વહાણની લઘુત્તમ લોડ ક્ષમતા, જે D ના દિવસોમાં બ Aટ 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.  નિષ્ક્રીય અભિગમ અંતરાલમાં દરેક મૂલ્યની તપાસ કરવા માટે હોઈ શકે છે જો તે ભાર ક્ષમતા ડી દિવસમાં સફળતાપૂર્વક પેકેટ્સને સ્થાનાંતરિત કરી શકે છે અને તેમાંથી લઘુતમ પસંદ કરી શકે છે. નિષ્કપટ અભિગમ માટેની સમયની જટિલતા લંબાઈ * એન હશે.

રેખીય શોધની જગ્યાએ બાઈનરી સર્ચનો ઉપયોગ કરીને આપણે સમયની જટિલતામાં સુધારો કરી શકીએ છીએ.

નો ઉપયોગ કરીને સમય જટિલતા દ્વિસંગી શોધ અભિગમ લોગ (લંબાઈ) * એન હશે.

અમલીકરણ

ડી + ડેઝ લિટકોડ સોલ્યુશનમાં પેકેજો શિપ કરવા માટે ક્ષમતા માટે સી ++ કોડ

#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

ડી ડેટસ લિટકોડ સોલ્યુશનમાં પેકેજો શિપ કરવા માટેની ક્ષમતાનું જટિલતા વિશ્લેષણ

સમયની જટિલતા

ઉપરોક્ત કોડની સમય જટિલતા છે ઓ (એન * લ logગ (લંબાઈ)) કારણ કે આપણે વેઇટ એરે લોગ (લંબાઈ) વખત પસાર કરી રહ્યા છીએ. અહીં n અને લંબાઈ અનુક્રમે પેકેટોની સંખ્યા અને શોધ અંતરાલનું કદ છે.

જગ્યાની જટિલતા

ઉપરોક્ત કોડની અવકાશ જટિલતા છે ઓ (1) કારણ કે આપણે જવાબ સંગ્રહવા માટે માત્ર એક વેરીએબલ વાપરી રહ્યા છીએ.

સંદર્ભ