课程表 III

发表于

算法：贪心算法

 

题目

url：https://leetcode-cn.com/problems/course-schedule-iii

这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。

给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。

示例：

1
2
3
4
5
6
7
8
输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出: 3
解释: 
这里一共有 4 门课程, 但是你最多可以修 3 门:
首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。
第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。
第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。
第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。

提示:

整数 1 <= d, t, n <= 10,000 。
你不能同时修两门课程。

 

分析

  1. 按照结束时间对课程进行排序;
  2. 使用一个大顶堆来储存已经选择的课程的长度;
  3. 一旦发现安排了当前课程之后，其结束时间超过了最晚结束时间，那么就从已经安排的课程中，取消掉一门最耗时的

 

Java解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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);

		int time = 0;
		for (int[] c: courses) {
			 if(c[0] > c[1]) continue;
			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();
	}
}
public class App {
	public static void main(String[] args) {
		//int[][] courses = new int[][] {{100, 200}, {200, 1300}, {1000, 1250}, {2000, 3200}};
		int[][] courses = new int[][] {{914,9927},{333,712},{163,5455},{835,5040},{905,8433},{417,8249},{921,9553},{913,7394},{303,7525},{582,8658},{86,957},{40,9152},{600,6941},{466,5775},{718,8485},{34,3903},{380,9996},{316,7755}};
		int ret = new Solution().scheduleCourse(courses);
		String out = String.valueOf(ret);
		System.out.print(out);
	}
}