პაკეტის გაგზავნის შესაძლებლობა D დღის განმავლობაში Leetcode Solution


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon
Array ორობითი ძებნა

პრობლემის განცხადება

პრობლემში ”პაკეტების გაგზავნის შესაძლებლობა D დღის განმავლობაში”, ჩვენ გვაქვს პორტები A პორტში, რომლებიც უნდა გადავიდეს B პორტში D დღეში.

ჩვენ გვეძლევა წონის მასივი, რომელიც შეიცავს თითოეული პაკეტის წონას და იმ დღეების რაოდენობას, რომელშიც ჩვენ უნდა გადავიტანოთ პაკეტები. ჩვენი ამოცანაა ვიპოვოთ გემის მინიმალური დატვირთვის მოცულობა, რომელიც გამოყენებული იქნება პაკეტის A პორტიდან B პორტამდე D დღის განმავლობაში გადასატანად.

leetcode გამოსავალი მოცულობის გაგზავნის პაკეტების D დღის განმავლობაში

მაგალითი

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 დღეში.

მიდგომა პაკეტის გადაზიდვის შესაძლებლობისა D დღის განმავლობაში Leetcode Solution

ამ პრობლემის გადასაჭრელად პირველი და ყველაზე მთავარია დაკვირვების გამოტანა. აქ მოცემულია რამდენიმე დაკვირვება ჩვენი ძიების ინტერვალისთვის:

  1. გემის დატვირთვის მოცულობა უნდა იყოს მინიმუმ ტოლი პაკეტისა, რომლის მაქსიმალური წონაა (მაქსიმალური). მოდით დავასახელოთ როგორც დაიწყე.
  2. გემის მაქსიმალური ტევადობა შეგვიძლია შევზღუდოთ ყველა პაკეტის წონის ჯამით, რაც ჯამია (წონა). მოდით ასე დავარქვათ დასასრული.

ახლა ჩვენ გვაქვს ჩვენი ძიების ინტერვალი. დავუშვათ, ინტერვალის ზომაა სიგრძე და პაკეტების რაოდენობაა n.  გულუბრყვილო მიდგომა შეიძლება იყოს ინტერვალის თითოეული მნიშვნელობის შემოწმება, თუ ამ დატვირთვის მოცულობამ შეიძლება პაკეტები წარმატებით გადაიტანოს D დღეში და შეარჩიოს მათგან მინიმუმი. დროებითი სირთულე გულუბრყვილო მიდგომისთვის იქნება სიგრძე * n.

ჩვენ შეგვიძლია გავაუმჯობესოთ დროის სირთულე ორობითი ძიების გამოყენებით ხაზოვანი ძიების ნაცვლად.

დროის სირთულე იყენებს ორობითი ძებნა მიდგომა იქნება log (სიგრძე) * n.

განხორციელება

C ++ კოდი, პაკეტის გაგზავნის შესაძლებლობისთვის D დღის განმავლობაში Leetcode Solution

#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

ჯავის კოდი შესაძლებლობების გაგზავნის პაკეტების D დღის განმავლობაში Leetcode Solution

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

D დღის განმავლობაში Leetcode Solution– ის პაკეტების გადაზიდვის შესაძლებლობების სირთულის ანალიზი

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n * ჟურნალი (სიგრძე)) რადგან ჩვენ ვათვალიერებთ წონის მასივის ჟურნალს (სიგრძე) ჯერ. აქ n და სიგრძე არის შესაბამისად პაკეტების რაოდენობა და ძიების ინტერვალის ზომა.

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან პასუხის შესანახად ვიყენებთ მხოლოდ ცვლადს.

ლიტერატურა