CourseScheduleIII.java

/* (C) 2024 YourCompanyName */
package greedy;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created by gouthamvidyapradhan on 27/06/2017.
 *
 * <p>There are n different online courses numbered from 1 to n. Each course has some
 * duration(course length) t and closed on dth day. A course should be taken continuously for t days
 * and must be finished before or on the dth day. You will start at the 1st day.
 *
 * <p>Given n online courses represented by pairs (t,d), your task is to find the maximal number of
 * courses that can be taken.
 *
 * <p>Example: Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] Output: 3 Explanation:
 * There're 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.
 *
 * <p>Note: The integer 1 <= d, t, n <= 10,000. You can't take two courses simultaneously.
 *
 * <p>Solution: O(N log N) 1. Sort the courses with earliest deadline time (Greedy sort) 2. Maintain
 * a max-heap of course duration. 3. Iterate through each course and increment the total time by
 * current course time and include this in the max-heap created in step 2. 4. If the total time
 * exceeds the current course deadline then, remove the course with max duration from max-heap
 * inorder to accommodate the new course.
 */
public class CourseScheduleIII {
  public static void main(String[] args) throws Exception {
    int[][] course = {{5, 5}, {2, 6}, {4, 6}};
    System.out.println(new CourseScheduleIII().scheduleCourse(course));
  }

  public int scheduleCourse(int[][] courses) {
    Arrays.sort(courses, (a, b) -> a[1] - b[1]);
    Queue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    int time = 0;
    for (int[] course : courses) {
      time += course[0];
      pq.add(course[0]);
      if (time > course[1]) time -= pq.poll();
    }
    return pq.size();
  }
}