LeetCode关于课程及会议安排的题目

关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers

---

LeetCode题目：630. Course Schedule III
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.

Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

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.

Note:

• The integer 1 <= d, t, n <= 10,000.
• You can't take two courses simultaneously.

class Solution {
    public int scheduleCourse(int[][] courses) {
        /*
        It is always profitable to take the course with a smaller end day prior to a course with a larger end day.
        */
        
        // 课程按照结束时间排序
        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) {
            // 如果能在end time之前结束，则将该课程加入队列
            if (time + c[0] <= c[1]) {
                queue.offer(c[0]);
                time = time + c[0];
            }
            // 如果当前最大的duration大于这个task的duration，则移除最大的duration
            else if (!queue.isEmpty() && queue.peek() > c[0]) {
                time = time - queue.poll();
                queue.offer(c[0]);
                time = time + c[0];
            }
        }
        
        return queue.size();
        
    }
}

LeetCode题目：253. Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null) return 0;
        if(intervals.length <= 1) return intervals.length;
        
        // 根据开始时间排序
        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) { return a.start - b.start; }
        });

        // 最小堆来模拟会议室，按照各个会议室中会议的结束时间排序
        PriorityQueue<Interval> rooms = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) { return a.end - b.end; }
        });

        // 从最早开始的会议开始
        heap.offer(intervals[0]);

        // 遍历后续的会议
        for (int i = 1; i < intervals.length; i++) {
            // 从最小堆中得到最早结束的会议室
            Interval interval = heap.poll();

            // 如果之前的会议已经结束了，则把当前会议安排在同一个会议室，更新结束时间
            if (intervals[i].start >= interval.end) {
                interval.end = intervals[i].end;
            }
            else {
                // 否则，需要安排一个新的会议室
                heap.offer(intervals[i]);
            }

            heap.offer(interval);
        }
        
        return heap.size();
    }
}