I thought the proof should prove that the algorithm solves the scheduling problem and also prove that the solution is always optimal (always finds the maximum number of disjoint/non-overlapping tasks).
From an implementation perspective, if you use a set there is no guarentee that you can check the most recent end time against your current start time in O(1) time because sets are unordered. I think using an array and checking the last element in the array against your jth element would give you the desired O(n) in the for loop. But thank you for the explanation, great vid!
Don't you have to prove that A is optimal, not that everything in A is compatible? Also, isn't this proof a bit circular? Your goal is to show that if you add j to A, everything is still compatible. But the reason for it is because if you add j to A, it must mean that everything is compatible.
I've, indeed, only added a correctness proof of the algorithm, in this video. This proof is, of course, necessary before showing that A is optimal. It would, indeed, be useful to add a proof of optimality for this algorithm. That could be the subject of another video. :) Regarding your second question, the proof is not circular. However, the step is, indeed, a bit 'trivial', as the condition in the pseudocode states that j should be compatible with A. I formulated the condition like this, so that it would simplify the pseudocode and eventually the proof. The condition itself is still simple enough to implement, so it shouldn't cause any problem. I hope that answers your questions. Thanks for your comment! :)
Instead of sorting the jobs in the ascending order of earliest finish time, can we choose to sort the jobs in the descending order of farthest start time? Is it optimal.. Can you explain for this case?
I guess we need to prove the elements in result are compatible and the number of elements in the set is maximum(optimal). you proved elements compatibility but u missed the maximum result set part.
What about the following problem: We are given n activities (each with starting and ending times) and also q plans (also with starting and ending times). Now we want to determine for every plan the maximal amount of activities we can do during that time interval. How could we solve this problem efficiently? That is, without having to iterate through all the activties in the plan intervals over and over again which would lead to a time complexity of O(nq + nlogn) (nlogn for sorting in the beginning and then n time for every plan). What could we do to make this term nq smaller?
Hi, so basically like activity selection we are looking for the next activity start time must be bigger than the current activity finish time so that we could find a series of back to back activity/job. That way we could populated more activity/job in a given time, right? Sometimes the questions with different name kind of confused me but after reading them over slowly and watching this video too kinda make sense.
What part of the proof isn't clear to you yet? Assuming that you understand the base case, I'll elaborate a bit on the induction step. In the induction step you show that, based on the induction hypothesis, the set of activities, but now including another activity (namely j), is still compatible. I do this by creating an exhaustive distinction; j hasn't been added to A and j has been added to A, respectively. If j hasn't been added, then A is still compatible, as you assumed in the IH that the set of activities without j is compatible. If j has been added, then line 4 of the pseudocode (4:11) must have been true and thus is j compatible with A. Thus all activities in A will still be compatible if j has been added to A. Therefore, when including another activity, all activities in A will always still be compatible. Did this extra explanation clarify your comment? :)
+MisterCode Thanks sir for a perfect explanation. I just got your proof. I was bit confused in the 2nd line of the Inductiin step. If j is not an element in A in that line i
I thought the proof should prove that the algorithm solves the scheduling problem and also prove that the solution is always optimal (always finds the maximum number of disjoint/non-overlapping tasks).
"so too bad for a pretty girl, we're not going to date her today." ikr, programmers never date
Thank you so much! You help me so much in school!
From an implementation perspective, if you use a set there is no guarentee that you can check the most recent end time against your current start time in O(1) time because sets are unordered. I think using an array and checking the last element in the array against your jth element would give you the desired O(n) in the for loop. But thank you for the explanation, great vid!
this was so useful ily tysm ;-;
Don't you have to prove that A is optimal, not that everything in A is compatible?
Also, isn't this proof a bit circular? Your goal is to show that if you add j to A, everything is still compatible. But the reason for it is because if you add j to A, it must mean that everything is compatible.
I've, indeed, only added a correctness proof of the algorithm, in this video. This proof is, of course, necessary before showing that A is optimal. It would, indeed, be useful to add a proof of optimality for this algorithm. That could be the subject of another video. :)
Regarding your second question, the proof is not circular. However, the step is, indeed, a bit 'trivial', as the condition in the pseudocode states that j should be compatible with A. I formulated the condition like this, so that it would simplify the pseudocode and eventually the proof. The condition itself is still simple enough to implement, so it shouldn't cause any problem.
I hope that answers your questions. Thanks for your comment! :)
The proof is just stupid
Great Video! Now I unterstand the algorithm.
Great video! It really helped clarify the algorithm.
thanks
Instead of sorting the jobs in the ascending order of earliest finish time,
can we choose to sort the jobs in the descending order of farthest start time? Is it optimal.. Can you explain for this case?
everyting but the prove was nice, ty
what is the cost of checking activity j is compatible with A? I think it should be 1+2+...+n = O(n^2). A little bit confused about that.
I guess we need to prove the elements in result are compatible and the number of elements in the set is maximum(optimal). you proved elements compatibility but u missed the maximum result set part.
What about the following problem: We are given n activities (each with starting and ending times) and also q plans (also with starting and ending times). Now we want to determine for every plan the maximal amount of activities we can do during that time interval. How could we solve this problem efficiently? That is, without having to iterate through all the activties in the plan intervals over and over again which would lead to a time complexity of O(nq + nlogn) (nlogn for sorting in the beginning and then n time for every plan). What could we do to make this term nq smaller?
If each activity associated with Profit(>=0) Can you apply greedy to maximize Profit instead of maximizing no of activities ?
You didn't prove that the algorithm maximizes the the amount of activities.
Is this prove for checking feasiblity of interval scheduling?
+MisterCode so this algorithm produces always an optimal solution?
whats the difference between activity selection problem nd interval scheduling problem?
There is no main difference. They basically describe the same problem.
Good question!
+MisterCode okk..thank you.!
Hi, so basically like activity selection we are looking for the next activity start time must be bigger than the current activity finish time so that we could find a series of back to back activity/job. That way we could populated more activity/job in a given time, right? Sometimes the questions with different name kind of confused me but after reading them over slowly and watching this video too kinda make sense.
I would have made 8-10 compatible at all costs.
your name is mr code..............................
I am not convinced
Can't understand the proof.
What part of the proof isn't clear to you yet?
Assuming that you understand the base case, I'll elaborate a bit on the induction step.
In the induction step you show that, based on the induction hypothesis, the set of activities, but now including another activity (namely j), is still compatible. I do this by creating an exhaustive distinction; j hasn't been added to A and j has been added to A, respectively. If j hasn't been added, then A is still compatible, as you assumed in the IH that the set of activities without j is compatible. If j has been added, then line 4 of the pseudocode (4:11) must have been true and thus is j compatible with A. Thus all activities in A will still be compatible if j has been added to A. Therefore, when including another activity, all activities in A will always still be compatible.
Did this extra explanation clarify your comment? :)
+MisterCode Thanks sir for a perfect explanation. I just got your proof. I was bit confused in the 2nd line of the Inductiin step.
If j is not an element in A
in that line i
You're welcome! Good job. :)
If j is not an element of A, then all activities (including j, so i
+MisterCode Thanks sir for a very quick reply. This will really help me in my greedy solution to my research problem, hopefully :) ✌
No problem. Good luck! :)
soodoh code