Python, Straightforward with Explanation


  • 33

    Sort all the courses by their ending time. When considering the first K courses, they all end before end. A necessary and sufficient condition for our schedule to be valid, is that (for all K), the courses we choose to take within the first K of them, have total duration less than end.

    For each K, we will greedily remove the largest-length course until the total duration start is <= end. To select these largest-length courses, we will use a max heap. start will maintain the loop invariant that it is the sum of the lengths of the courses we have currently taken.

    Clearly, this greedy choice makes the number of courses used maximal for each K. When considering potential future K, there's never a case where we preferred having a longer course to a shorter one, so indeed our greedy choice dominates all other candidates.

    def scheduleCourse(self, A):
        pq = []
        start = 0
        for t, end in sorted(A, key = lambda (t, end): end):
            start += t
            heapq.heappush(pq, -t)
            while start > end:
                start += heapq.heappop(pq)
        return len(pq)
    

    (With thanks to @uwi - see his solution here)


  • 9
    M

    Great Solution. Here is my java solution.

    public class Solution {
    
        public int scheduleCourse(int[][] courses) {
            int n = courses.length;
            if (n == 0) return 0;
            Arrays.sort(courses, (a, b) ->  a[1] - b[1]);
            PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
            int start = 0;
            for (int[] course: courses) {
                start += course[0];
                pq.offer(course[0]);
                if (start > course[1]) {
                    start -= pq.poll();
                }
            }        
            return pq.size();
        }   
    }
    

  • 14
    C

    We can safely replace the while statement at while (start > course[1]) by if statement, and it will still work. This is because each time we only need to remove at most one element from the pq.


  • 0
    A

    Thanks, pretty deep thought.


  • 0
    Y

    Elegant and straightforward, Thanks


  • 1
    Z

    Thanks for the code! Here is my C++ solution. Theoretically it may improve performance if sorting courses based on a[1] < b[1] || (a[1] == b[1] && a[0] < b[0]), because the shorter course with same deadline will be upfront. It saves some pop and push.

    class Solution {
    public:
        int scheduleCourse(vector<vector<int>>& courses) {
            sort(courses.begin(), courses.end(), mycompare);
            priority_queue<int> pq;
            int n = courses.size(), cur = 0;
            for (auto course:courses) {
                if (cur + course[0] <= course[1]) { 
                    pq.push(course[0]);
                    cur += course[0];
                }
                else if (course[0] < pq.top()) {
                    cur += course[0]-pq.top();
                    pq.pop();
                    pq.push(course[0]);
                }
            }
            return pq.size();
        }
    private:
        static bool mycompare(vector<int>& a, vector<int>& b) {
            return a[1] < b[1] || (a[1] == b[1] && a[0] < b[0]);
        }
    };
    

  • 0
    M

    @CoderLeung
    Nice catch.


  • 0
    L

    @awice start -= heapq.heappop(pq)


  • 1

    @larabear My code AC's. In Python, heapq does a minheap by default, so I am putting -t onto the heap instead of t to make it function as a maxheap. Thus, I want to add heapq.heappop(pq) instead of subtract.


  • 0
    S

    I think

    while start > end:
       start += heapq.heappop(pq)
    

    can be replaced with

    if start > end:
       start += heapq.heappop(pq)
    

    because in (k-1)th iteration start <= end , so in kth iteration, start is the (k-1)th start plus kth course's length.
    After it's minus the maximum length of the first k course it should be no larger than (k-1)th end thus no larger than kth end.


  • 1
    S

    **A rigorous proof of optimality for this greedy algorithm.**

    • First, we want to show that the courses in the optimal solution must appear in ascending order with respect to their end time.

    Consider two adjacent courses a and b in the optimal solution, where a is prior to b. If there exists da>db, where da and db refer to the end time of a and b respectively, then we can swap a and b here. After swapping, the courses before a and the courses after b will NOT be affected. Besides, it is easy to see that the solution is still feasible due to the fact that da>db, where we have t0 + ta + tb < db < da, assuming course a starts at time t0 and ta, tb are the duration of a and b respectively.
    Now we can perform this swapping process to each adjacent pair until all the adjacent a, b satisfy da <= db, like the bubble sorting. After all, we still have a feasible solution with the same number of courses taken and this contradicts the optimality of the original solution. Therefore, we have proved our argument.

    • Second, since we know that the optimal course list should appear in ascending order by the courses' end time, how shall we choose the courses?

    We just select the course one by one in ascending order. Once there is a conflict when we choose the Kth course, it means that we cannot put all the K courses in the candidate list. In other words, one course must be removed from the candidate list. Which one should we remove?
    Obviously, the one with the largest duration. Supposing the courses already chosen in the candidate list is c1, c2, ..., ck with duration t1, t2, .., tk, then we find the maximum, say cj, and remove it. Now the total duration of the k-1 courses will be <= d_(k-1) because we have replaced cj with ck while tk<=tj. Then it follows that the total duration <=d_(k-1)<=d_k since we choose course in ascending order of the end time, which indicates d_(k-1)<=d_k. Therefore, by removing the longest course, we get a feasible partial solution now. By removing the longest duration course to eliminate conflicts, we ensure that we have saved most time for the remaining courses, that is, the remaining courses can start at an earliest possible time. Therefore, this will lead to an optimal solution. Continue this process until we have exhausted all the courses.

    import heapq
    
    class Solution(object):
        def scheduleCourse(self, courses):
            """
            :type courses: List[List[int]]
            :rtype: int
            """
            s = []
            start = 0
            for t, end in sorted(courses, key=lambda c: c[1]):
                start += t
                heapq.heappush(s, -t)  # max heap
                if start > end:
                    nt = heapq.heappop(s)  # the newly pushed t may also be poped
                    start += nt  # nt is the negative t
            return len(s)

  • 0
    L

    @awice You don't need a while loop since after every iteration you'll do the check and pop it so that it's less than the end.


  • 0

    @livelearn The third person to comment this in this thread, but I'm not sure what you want me to do about it.


  • 0
    L

    @awice Sorry didn't read the comments before, just thought you might have missed it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.