leetcode-course-schedule-iii

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/course-schedule-iii

　　给了一系列的二元组的数组，第一个元素代表课程花费时间，第二个代表课程deadline。问一共能最多能完成多少门课程，两门课程不允许有交叠。

题目分析

　　从题目明显可以看出来是贪心题，可是没有想出来好的思路，参考了讨论区的一个答案 https://discuss.leetcode.com/topic/93712/python-straightforward-with-explanation 整理一下关键的思路：

  1. 按deadline逆序排序，也就是说优先考虑deadline靠前的课程
  2. 记录一个start值，表示下次课程的起始时间，也就是说start值每次都要加上当前课程的花费时间。但是，当start加上当前course的花费时间以后，如果超过了当前课程的deadline，那么明显是不符合要求的，也就是说此时应该移除之前已经纳入考虑范围的课程，应该移除的是那些花费时间最大的课程，很容易可以理解用大根堆记录课程花费时间，当start加上花费时间大于deadline时，移除大根堆的最大元素，一定可以保证小于deadline了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int scheduleCourse(int[][] courses) {
        int n = courses.length;
        Arrays.sort(courses, (a, b) ->  a[1] - b[1]); // 按endtime倒序排列
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // 大根堆
        int start = 0;
        for (int[] course: courses) {
            start += course[0]; // 先加到start中
            pq.offer(course[0]); // 先加到pq中
            if (start > course[1]) { // 如果start超过deadline，移除堆顶元素，一定可以保证start小于end
                start -= pq.poll();
            }
        }        
        return pq.size();
    }   
}

　　时间复杂度：nlogn