Simple Python code using priority queue with explanation

• ``````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)

``````

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