05 August 2008
给一堆课程，这些课程每个都有duration的时间和结束时间，返回最多可以修几门课
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
31
32
33
34
35
36
37
38
39
40
41
Keep a max heap in order of course with higher duration first.
Sort the array in increasing order of lastDay in order to check those courses first which are ending before the rest.
Add the duration of current course to time and add the course to the heap.
If the time exceeds the lastDay of the current course, then remove the course from the heap which had the highest duration, i.e. the top of the heap and reduce the duration of this course from time.
Finally, the heap will contain all the courses that can be done, so return heap.size() as your result. ```java class Solution {
public int scheduleCourse (int [][] courses) {
if (courses.length == 0 || courses == null)
return 0;
// Keep a max heap w.r.t. higest duration, i.e. courses [i][0]
Queue <int []> heap = new PriorityQueue (new Comparator <int []> () {
public int compare (int a [], int b []) {
if (a [0] < b [0])
return 1;
else if (a [0] > b [0])
return -1;
else
return 0;
}
});
// Sort courses in increasing order of lastDay, i.e. courses [i][1]
Arrays.sort (courses, new Comparator <int []> () {
public int compare (int a [], int b []) {
if (a [1] > b [1])
return 1;
else if (a [1] < b [1])
return -1;
else
return 0;
}
});
int time = 0;
for (int i = 0; i < courses.length; i++) {
time += courses [i][0];
heap.add (courses [i]);
if (time > courses [i][1])
time -= heap.poll()[0];
}
return heap.size();
} } ```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses,(a,b)->a[1]-b[1]); //Sort the courses by their deadlines (Greedy! We have to deal with courses with early deadlines first)
PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->b-a);
int time=0;
for (int[] c:courses)
{
time+=c[0]; // add current course to a priority queue
pq.add(c[0]);
if (time>c[1]) time-=pq.poll(); //If time exceeds, drop the previous course which costs the most time. (That must be the best choice!)
}
return pq.size();
}
}