Simple Python code using priority queue with explanation


  • 0
    D
    class Solution:
        def scheduleCourse(self, courses):
            """
            :type courses: List[List[int]]
            :rtype: int
            """
            import heapq
            sorted_courses = sorted(courses, key=lambda x: x[1])
            start = 0
            completed_courses = []
    
            """
            Sort courses in ascending order of deadline
            Maintain a priority queue based on the length of the course
            At each deadline/course, check whether this course can meet deadline or not
            If the course can not meed deadline, remove the longest course if the priority queue if the length
            of the longest course if smaller than this course
            """
    
            for t, d in sorted_courses:
                if d >= start + t:
                    # we want a max heap, therefore need to use -t instead
                    heapq.heappush(completed_courses, -t)
                    start += t
                else:
                    t_longest = completed_courses[0]
                    if t <= -t_longest:
                        heapq.heappop(completed_courses)
                        heapq.heappush(completed_courses, -t)
                        start -= (-t_longest - t)
            return len(completed_courses)
    
    

Log in to reply
 

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