BS-15. Capacity to Ship Packages within D Days
HTML-код
- Опубликовано: 5 окт 2024
- Problem Link: bit.ly/43QDpdG
Notes/C++/Java/Python codes:
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/take...
0:00 Introduction of Course
![Eminem - Temporary (feat. Skylar Grey) [Official Music Video]](http://i.ytimg.com/vi/ZaK9Wi5ho0o/mqdefault.jpg)
bhaiya i have done the last two problems on my own without watching your solution and now i am gaining a little bit of confidence that i can also do.... it is not that i haven't done any problem on my own but it was after completing your playlist of that topic and then doing other problem of that topic, but it is the first time i am doing this before completing this playlist of binary search,,, thank you bhaiya , you teaching style is just awesome😍😇😇
gawd
dude exactly same, i was also able to solve this one and the last one on my own. this happened for the first time!!
@@arujgarg7267 Exactly same... Solved this and previous 2 problems on my own
solved it on my own , woohoo confidence is just sky rocketing !! thank you striver
which clg?
aapki videos shuru majboori mei kiye the,
lekin ab maza aane laga hai :)
sammmmee😂
The way you explain and write the code so clearly is what is so unique about you. Clearly understood, thanks!
bro this is one of the best cheat sheet.
the way you split each patterns into sub patterns is great
Would be great if you continue to find sub patterns within existing patterns
SALUTE HAI BHAI..!! kya smjhaya hai ..itna easy logic!!... blown away! Thank you rahega
One more thing that should be added into the question is that the weights need to shipped in order. I think if we are to club the minimum and the maximum weights together then 11 would be the answer for this [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Days = 5
Ikr, right now the question seems more like binary search over series of knapsacks instead of contiguous sums
yup, i was literally thinking the same thing, i thought if i only take consecutive days i might get error in leetcode.
I watched 5 videos and was trying to understand this for last 3 days, but the way you explained it has become like cutting butter for me now..thanks a lot
Can u share where were doing this problem, was it a platform other than leetcode ? Kindly share
❤understood, next level lecture , this is what the tier 3 students wish to listen in classroom
man..even this one i coded down myself...understanding the previous ones...thanks bhai
Was able to solve this on my own. This question is similar to minimum days to make m bouquets. Thanks a tonne, Striver !!!!
For Least Never Return at first if you get desired answer store it in answer variable and check it till end if there still exists lesser value
Thank You Striver.
your are totally amazing striver bhai , i got the solution after your explanation 💓💓
At 15:11 bhaiya you said high=23, but actually mid was=32 before, so new high=mid-1=32-1=31
hnn bhaii mee bhi yhi soch rhaa thaa tbbhi comment dhundh rha tha ki kisi nee to kia hogaa
mistake at 15:03 it will come to 31 not 23, but its ok. under stood.
agree
yeah
Wow...the portrait of the ship is so good 😃
I was able to code in less than 7 mins (thala for a reason....naah, obv u the reason).....thanks a lot.
sorry to say but studying DSA with you and LOVE sir combined is just better than best
love babbar?
@@TheLearningLab898 yaaa
Where are you placed now??
Crystal clear explanation striver... Clearly understood everything...Thanks a lot for this awesome series.
Thanks man! you make the code look so simple, Idk why I end up writing a long and complex brute force code even though it works..
wow man, i could able to solve this on my own. i am watching this because i just wanna see your explination, i am following your playlist, learning in a structure and doing similar problem really helps in undertanding the concept, thank man. also after solving koko banana problem, solving prev problem in this playlist find the smallest divisor, really cake walk.
tha't it, tho i don't comment that much, you are helping many ppl like me. thanks for doing all the work.
thank u striver bhaiyaa!you made divide and conquer a cakewalk! this ecstatic feeling is so morale boosting as i did this problem by myself in a single go under your guidance ! much love
superb explanation, 80% coded it myself, tysmm
slight improvement, the max can also be sum(weights)-days+1. This is because in worst case you can ship the item with max weight on day 1, then remaining items combination on each days
Amazing explanation as always Understood
S + T + R + I + V + E + R = 7 , Thala for a reason
Another code for same approach:-
bool f(int mid, vector &weights, int d){
int day = 1, temp = mid;
for(int i=0;i
Woah ive got a similar approach as well
class Solution {
public:
bool check(vector& v, int mid, int days) {
int tmp = mid;
for (auto e : v) {
if (tmp >= e) {
tmp -= e;
} else {
days--;
if (days == 0) {
return false;
}
tmp = mid;
tmp -= e;
}
}
return true;
}
int shipWithinDays(vector& v, int d) {
int low = *max_element(v.begin(), v.end());
int high = accumulate(v.begin(), v.end(), 0);
int ans;
while (low
bhaiya i was able to solve the problem on my own without watching your solution, tysm bhaiya 🙂
- [00:17](ruclips.net/video/Mde2q7GFCrw/видео.html) The problem is about finding the minimum capacity needed to ship packages within a given number of days.
- [01:49](ruclips.net/video/Mde2q7GFCrw/видео.htmlm49s) An example is given where if the ship's capacity is 100, all packages can be shipped in one day.
- [03:22](ruclips.net/video/Mde2q7GFCrw/видео.htmlm22s) It is demonstrated that a capacity of 10 leads to shipping taking more than the given number of days.
- [04:20](ruclips.net/video/Mde2q7GFCrw/видео.htmlm20s) Increasing the capacity to 15 allows shipping all packages within the given days.
- [06:11](ruclips.net/video/Mde2q7GFCrw/видео.htmlm11s) The answer must be between the maximum weight of a product and the sum of all weights.
- [08:01](ruclips.net/video/Mde2q7GFCrw/видео.htmlm1s) A function is described to find the number of days required to ship with a given capacity.
- [12:32](ruclips.net/video/Mde2q7GFCrw/видео.html2m32s) The initial solution has a time complexity of O(N^2) due to linear search.
- [13:54](ruclips.net/video/Mde2q7GFCrw/видео.html3m54s) Binary search is introduced as an optimization technique to find the minimum capacity needed.
- [16:49](ruclips.net/video/Mde2q7GFCrw/видео.html6m49s) The binary search approach eliminates capacities that are not possible and updates the answer with the lowest possible capacity.
- [18:25](ruclips.net/video/Mde2q7GFCrw/видео.html8m25s) The time complexity of the binary search solution is O(N * log(Sum - Max)), where N is the number of items and Sum and Max are the sum of weights and the maximum weight, respectively.
- [19:50](ruclips.net/video/Mde2q7GFCrw/видео.html9m50s) The C++ code for the binary search solution is demonstrated, and viewers are encouraged to find code for other programming languages in the video description.
Understood! Super excellent explanation as always, thank you very much for your effort!!
2 things to keep in mind
The range is - low (max of all the weights), high (summ of all the weigths)
The logic for helper function will do day++ if the load value is not.
UnderStood
*Completed now, thanks for such lovely content.*
Thank You Striver understood everything🙂
Understood
Thank You striver for such an amazing explanation
solved it on my own, yay!
Understood! Thanks :)
Understood Very Well!
well well well now i am solving leetcode medium question without any help in the optimal way thank you striver!
i was able to do it by myself...........thanks to striver;
return happy😆;
solved by myself, All thanks to you.
understood the complete concept
understood striver ,thank you so much
It was just an awesome video... but pls tell me... why int days is initialised with 1 .... why not int days=0;
you are artist too bro, multitalented striver
mast habibi
Understood and solved by myself
bhaiya timestamp 15:06
here mid-1=high=point 31 ,not point 23.
same I was searching for this comment 😅
Man, you're legend🤓. Thanks
nice explanation
Understood
Understood!
what's the overall time complexity of binary search algorithm in this question
Because first loop to find summation and maximum element takes O(n) and then the binary search algo which takes (log2(sum-maxi)), after the algo we call the findDays function which take O(n) time complexity.
so, what's the time complexity of the code
Thanks You!!
It would be O(n*log(sum-max)), but if you want the exact time complexity taking into account the summation and maximum, then O(2n + n*log(sum-max)).
concise and helpful explaination
Possible function takes time to understand but clear now
bool isPossible(vector &weights, int d, int mid){
int dayCount = 1;
int sum = 0;
for(int i = 0; i < weights.size(); i++){
sum += weights[i];
if(sum d){
return false;
}
sum = weights[i];
}
}
return true;
}
Thanks a lot Bhaiya. You make it easy peasy problem 😀
Understood, thank you.
NICE SUPER EXCELLENT MOTIVATED
Amazing question
🔥🔥🔥🔥🔥🔥🔥🔥
Bro by when your whole dsa sheet will be covered, placement coming up?any eta approx?
@striver please make full dsa paid or free course for competitive programming. I am watching your videos from past 5 months but still I am unable to solve new problems or codeforces ,codechef problems
Can u make paid live full course .
I am highly requested to u please launch your course from basic to advanced competitive course. programming course
join tle-eliminators
@@takeUforward please launch paid cp course we want to learn from you, you explain very well
Living Legend!
Understood !! 😍😍
Nice explanation
I have doubt in first example the answer must be 11 as you can take 1st and last element sum everytime so it will be 11
You need to take consecutive elements :)
Can anyone look up at my code and find mistake . I got wrong answer of this ques i.e capacity to ship packages within d days .
class Solution {
public:
int caldays(vector& weights, int cap){
int sum=0, cnt=0;
for(auto it: weights){
sum+=it;
if(sum
Low has to start from the maxElement in the array, other then that I see no error...
min days will be 1 not 0, just change days = 0 to days = 1 in the caldays function, also start low from the max element in the weights array
@@swapnil243 Correct
@@swapnil243 but it will. Without changing days in cladays
Nice explanation 👌
if weights are 1 2 8 9 and d=2 will it give correct answer??
thank you bhaiya
Understood 🎉
going smoothly
🎉🎉🎉
Why the weights are not sorted then also it works, please let me know the function which is inside while loop
Understood✅🔥🔥
Well done
15:14 high should be 31 na?
yes but answer comes the same in this case
Atlast got it❤❤❤
understood
Understood ❤
Understood !!!!!
Thank you Bhaiya
Thanks❤
I think in linear search return the capacity not daysRquired
17:00 opposite polarity
Thank You
Superb sir ❤
Done for today
hi @striver , when to use while(high - low >1) condition
I don't use it anywhere, all problems can be solved without that, if your base is clear
all the question are similar to previous one
understooood :)
17:59 ✅
understood!
Day 2 till here
First comment
Isn't this same as painter partition problem?
why we are initializing days with 1
This problem is same as BOOK ALLOCATION PROBLEM
Undertsood
Understood Striver
"understood"