Scale Engineer

Course Schedule III

Hard
#0584Time: O(N log N). Sorting takes O(N log N). The loop runs N times, and each priority queue operation (offer, poll, peek) takes O(log K) time, where K is the number of courses taken so far (K <= N). This results in a total time complexity of O(N log N).Space: O(N) in the worst case, where the priority queue might store the durations of all N courses.2 companies
Patterns
Greedy
Algorithms
Sorting
Data structures
ArrayHeap (Priority Queue)
Companies
FlipkartWorks Applications

Prompt

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

 

Example 1:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Explanation: 
There are totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Example 2:

Input: courses = [[1,2]]
Output: 1

Example 3:

Input: courses = [[3,2],[4,3]]
Output: 0

 

Constraints:

  • 1 <= courses.length <= 104
  • 1 <= durationi, lastDayi <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most efficient approach, employing a greedy strategy. We process courses sorted by their deadlines. We tentatively take each course if possible. If taking a course violates its deadline, we check if we can swap it with a previously taken course that has a longer duration. This swap reduces the total time spent, potentially allowing us to take more courses overall.

Algorithm

  • Sort the courses array based on lastDay in ascending order.
  • Initialize a max-priority queue, pq, to store the durations of courses taken.
  • Initialize currentTime = 0.
  • For each course [duration, lastDay] in the sorted list:
    • If currentTime + duration <= lastDay:
      • Add the course: currentTime += duration, pq.offer(duration).
    • Else if the priority queue is not empty and its top element (max duration) is greater than the current duration:
      • Swap the courses: currentTime = currentTime - pq.poll() + duration, pq.offer(duration).
  • Return the size of the priority queue.

Walkthrough

The optimal strategy involves a greedy choice. First, we sort the courses by their lastDay. This ensures we prioritize courses that need to be finished earlier. We iterate through these sorted courses, maintaining a currentTime which tracks the total duration of courses taken so far.

For each course, we check if we can add it to our schedule. If currentTime + course.duration <= course.lastDay, it fits perfectly. We add its duration to currentTime and add the duration to a max-priority queue. The priority queue will store the durations of all the courses we've decided to take.

If the course doesn't fit (currentTime + course.duration > course.lastDay), we have a conflict. We can't simply add it. However, we can check if it's beneficial to swap this current course with one we've already taken. To make the schedule more flexible for future courses, we want to minimize the currentTime. This can be achieved by replacing the longest course taken so far with the current course, but only if the current course is shorter. We use the max-priority queue to find the longest course taken so far (its peek()). If pq.peek() > course.duration, we perform the swap: remove the max duration from pq and currentTime, and add the current course's duration instead. This reduces the total time and makes the schedule valid for the current course, while keeping the number of courses taken the same.

After iterating through all courses, the size of the priority queue gives the maximum number of courses we could take.

import java.util.Arrays;import java.util.Comparator;import java.util.PriorityQueue; class Solution {    public int scheduleCourse(int[][] courses) {        Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));                PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);        int currentTime = 0;                for (int[] course : courses) {            int duration = course[0];            int lastDay = course[1];                        if (currentTime + duration <= lastDay) {                currentTime += duration;                pq.offer(duration);            } else if (!pq.isEmpty() && pq.peek() > duration) {                currentTime += duration - pq.poll();                pq.offer(duration);            }        }                return pq.size();    }}

Complexity

Time

O(N log N). Sorting takes O(N log N). The loop runs N times, and each priority queue operation (offer, poll, peek) takes O(log K) time, where K is the number of courses taken so far (K <= N). This results in a total time complexity of O(N log N).

Space

O(N) in the worst case, where the priority queue might store the durations of all N courses.

Trade-offs

Pros

  • Optimal time complexity that passes for the given constraints.

  • Elegant solution combining sorting and a priority queue.

Cons

  • The greedy logic, specifically the swapping step, might not be immediately obvious to come up with.

Solutions

public class Course_Schedule_III { // https://leetcode.com/articles/course-schedule-iii/ public class Solution { public int scheduleCourse ( int [][] courses ) { Arrays . sort ( courses , ( a , b ) -> a [ 1 ] - b [ 1 ]); PriorityQueue < Integer > queue = new PriorityQueue <>(( a , b ) -> b - a ); // duration time放入heap int time = 0 ; for ( int [] c: courses ) { if ( time + c [ 0 ] <= c [ 1 ]) { queue . offer ( c [ 0 ]); time += c [ 0 ]; } else if (! queue . isEmpty () && queue . peek () > c [ 0 ]) { time += c [ 0 ] - queue . poll (); queue . offer ( c [ 0 ]); } } return queue . size (); } } } ############ class Solution { public int scheduleCourse ( int [][] courses ) { Arrays . sort ( courses , Comparator . comparingInt ( a -> a [ 1 ])); PriorityQueue < Integer > pq = new PriorityQueue <>(( a , b ) -> b - a ); int s = 0 ; for ( int [] course : courses ) { int duration = course [ 0 ], lastDay = course [ 1 ]; pq . offer ( duration ); s += duration ; if ( s > lastDay ) { s -= pq . poll (); } } return pq . size (); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem