Can you tell me what to do in case the finishing times of two activities are the same? Do we sort by the difference between their respective start and end times or do we sort according to the finish time of the previous activity? As for example, here why is A6 selected first instead of A4?
just wanna ask how did u guys sort the starting array? did u change the index value of starting array with respect to the finish array??? assuming after doing sort on finish array, then u sorted the starting array?
Sir,If I want to learn python , Then in the interview will they allow me to use built in libraries of it or how I am confused to choose that which language i have to learn it's just i have a very basic idea of Java ,python and javascript so which language would u suggest me to learn ...please guide me in this
How for unsorted input it will take nlogn can you elaborate ?? . I am thinking maybe this is the answer just verify . O() = O(sorting) + O(Activity Selection) = O(Quick sort average case) + '''" = nlogn + n = nlogn ??
Hi Achin, I have never heard of the local improvement/local exchange trick. Could you please share some resource? I can't find anything relevant on Google either.
I'm struggling to find an algorithm that works with these 2 tests in the cases when there is 1 person and 2 people able to perform tasks: [[1, 2], [4, 5], [6, 7], [3, 8]] should output: 3 (1 person), 4 (2 people) [[1, 4], [2, 6], [7, 9], [5, 10]] should output: 2 (1 person), 4 (2 people
If you are looking for an implementation of the problems in the video, you can refer the link given in the description. Here it is for this problem: www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/
Arey algorithm thodi ratni hoti hai. What is the intuition behind sorting by finish time and not start time? You know what's better than these GFG videos? Just copy gfg article text convert text to speech
So basically there are three ways to do the problem,but only one optimal way. 1) Let say you sort the array based on start time array ,Then there is this problem that the first activity you selected may take a huge amount of time but by then you would have done better if you would have opt for the remaining activities instead of this first one.(one way to justify the falseness). ............................................................................................................................................................................................................................................................................. 2) Now let say you didn't sort the array in any way and keep taking everything that comes in your way.(This is the worst thing anyone would do,I hope you know it well). ............................................................................................................................................................................................................................................................................. 3)Now comes your actual question i(why sort the based on the finish time right?) , So the obvious yet not obvious explanation is that when you sort activities based on end-times then as we choose those with min end-time ,we end up doing a lot of activities as we get across the first things first!!(just think about it)
Hi Vijay, I had the same doubt but It's not about Maximum weight Its about having Max no of activity. - a3,a2,a4 = 3 activity - a3,a2,a5,a6 = 4 activity.(winner) Also, the max weight in this example will be a1,a6
I love how calm you talk. Your accent is also very easy to understand. :) Good stuff.
🤣
I think for(j=i+1;j
Yess!!..
Like always! Simple and understanding❤
Can you tell me what to do in case the finishing times of two activities are the same? Do we sort by the difference between their respective start and end times or do we sort according to the finish time of the previous activity? As for example, here why is A6 selected first instead of A4?
The answer would be same whichever interval you take first.
I think we can just keep the one with largest start time when finish time is the same
Very nicely explained which gives clear explanation and helps to understand the chapter better.
please also discuss the algorithm analysis.
For the given problem, the time complexity is same as that of sorting the input, i.e., O(n log n).
Hi, can you please explain how you directly arrived at the 3 step algorithm for above problem?
Sir if suppose there is a clash i.e. if the ending time and starting time of 2 activities are same then what should be the approach?
If at all that kind of situation arises, then apparently you can select anyone of them but not both.
Excellent explanation
Very good explanation , concise and to the point.
its very good, keep doing good work!!
@geekforgeek
update kr lo Bhai .. way of teaching
But what if the question has multiple solutions, I mean to say what the max no of activities can be done starting from pos n rather than from 1st.
Then use dynamic programming. Greedy approach does not always give globally optimum solution.
Thanks from Turkey :))
very nice and clearly!! Thank you😊💕
the last example ithink we should sort them according to start time not end time
just wanna ask how did u guys sort the starting array?
did u change the index value of starting array with respect to the finish array???
assuming after doing sort on finish array, then u sorted the starting array?
use any method of sorting
First store value of start[i] and end[I] in pair and store this pair another vector and then sort that vector on the basis of second value of pair
Sir,If I want to learn python ,
Then in the interview will they allow me to use built in libraries of it or how I am confused to choose that which language i have to learn it's just i have a very basic idea of Java ,python and javascript so which language would u suggest me to learn ...please guide me in this
Doubt clear thanks buddy
short and sweet
please provide a detailed run time analysis since I was poor in calculating .
nice explanation
Thank you sir
if unsorted,using java we can use Array.sort() and then do the needful no?
if it's unsorted , then we have to sort them according to their finish time. So Arrays.sort() will not do the task, you have to use comparator.
What if in unsorted input we print sequence of activities while insertion/merge sort on input? Is it possible that we may loose data in such case?
Please increase the volume of the video
The sorting was not stable. what if it was (5,9) would have have came before(8,9) then how would you approach?
same approach since start time of (5,9) is less than the finish time of (5,7) so it will skip (5,9) and eventually print (8,9).
Why does it feel like the same person has given voice overs in Neso academy's digital electronics videos?
How for unsorted input it will take nlogn can you elaborate ?? . I am thinking maybe this is the answer just verify .
O() = O(sorting) + O(Activity Selection)
= O(Quick sort average case) + '''"
= nlogn + n
= nlogn
??
Sir your explanation is excellent ,but my humble request is run the code which is explained in video ,and upload along with this video
Please Improve the Quality of the video... 360p is a bit low.... and the code does not appear clearly because of it..
Neeraj Prakash you can have the code from geeksforgeeks site
Anyone please explain why we are always considering first time.
i beg you please tell about the Maximum Independent set ,Local Improvement or local exchange trick in Activity selection problem
Hi Achin,
I have never heard of the local improvement/local exchange trick. Could you please share some resource? I can't find anything relevant on Google either.
I'm struggling to find an algorithm that works with these 2 tests in the cases when there is 1 person and 2 people able to perform tasks:
[[1, 2], [4, 5], [6, 7], [3, 8]]
should output: 3 (1 person), 4 (2 people)
[[1, 4], [2, 6], [7, 9], [5, 10]]
should output: 2 (1 person), 4 (2 people
You can solve the problem by again calling the same function and check for the remaining elements, adding up both the results in the end.
are we using merge sort technique?
who gives a damn but probably quicksort
excellent, thank you
thanks
Can you explain me about activity compare.
how unsorted list has more time complexity then Sorted list??
Supriyo Mukherjee because there's a cost for sorting the list as well
if there is some cost associated with each activity and our goal is earn max cost by performing maximum activities,,,, will greedy work if yes how?
Lavkush Tiwari no you’ll need dynamic programming for that. Subscribe here if you’re interested in AI
tnx a lot
can u plzz tell how to write an algo of all these greedy methods
If you are looking for an implementation of the problems in the video, you can refer the link given in the description.
Here it is for this problem: www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/
Because of subtitles we cannot see the algorithm written...and even you are not telling that algorithm each and every letter
You can disable subtitles in the video (the button beside the button of quality/speed of the video)
we could have choosen A4 instead of A5. i am not clear why we choose A5
because finishing time of A5 is less than A4 and we have already sorted them according to their finishing time so A5 comes before A4.
if we choose A4 then we won't be able to select other activities after it which would result in less activities done.
what is stl sort
STL sort is not any kind of sort. STL is a modern format of C++ where sorting is an in built function
nice
Please use mic
in Activity Selection Problem code why you write i=j in program
because the present activity becomes the previous activity for the next activity
sexy explaination ....
Not understand
Worst audio with unclear explanation. I'm talking about whole playlist, this is genuine critisism
Arey algorithm thodi ratni hoti hai. What is the intuition behind sorting by finish time and not start time? You know what's better than these GFG videos? Just copy gfg article text convert text to speech
360p
👍
You don't discuss the proof of correctness, not fair!!
So basically this guy didnt explain why end time is taken for the sorting ordering. disliked.
So basically there are three ways to do the problem,but only one optimal way.
1) Let say you sort the array based on start time array ,Then there is this problem that the first activity you selected may take a huge amount of time but by then you would have done better if you would have opt for the remaining activities instead of this first one.(one way to justify the falseness).
.............................................................................................................................................................................................................................................................................
2) Now let say you didn't sort the array in any way and keep taking everything that comes in your way.(This is the worst thing anyone would do,I hope you know it well).
.............................................................................................................................................................................................................................................................................
3)Now comes your actual question i(why sort the based on the finish time right?) , So the obvious yet not obvious explanation is that when you sort activities based on end-times then as we choose those with min end-time ,we end up doing a lot of activities as we get across the first things first!!(just think about it)
please give a proper c code implementation for better understanding ,,
complete code in c
I can't see the example....Ur subtitle work as an obstacle
Thanks for the feedback. We will keep this in mind for further videos.
Meanwhile, you can turn off the subtitles for the video wherever necessary.
Ooo ok..thnq..
Not at all helpful
sir but if we select a3,a2,a4 instead of a3,a4,a5,a6 then more work would be done
Hi Vijay, I had the same doubt but It's not about Maximum weight Its about having Max no of activity.
- a3,a2,a4 = 3 activity
- a3,a2,a5,a6 = 4 activity.(winner)
Also, the max weight in this example will be a1,a6
"lets summarize these steps into a code"
That's not how English works..
it is not any literature video
content is good, video quality and accent aren't!
Nobody cares about the accent.