会议安排 II

Problem

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of days required to schedule all meetings without any conflicts.

Note: (0,8),(8,10) is not considered a conflict at 8.

Example 1:

Input: intervals = [(0,40), (5,10), (15,20)]

Output: 2

Explanation:

day1: (0,40)

day2: (5,10),(15,20)

Example 2:

Input: intervals = [(4,9)]

Output: 1

Constraints:

• 0 <= intervals.length <= 500
• 0 <= intervals[i].start < intervals[i].end <= 1,000,000

Idea

Sort the meetings by start time and use a min-heap that stores the end time of the last meeting on each day.

For each meeting, if the earliest-ending day is already free (heap top <= start), reuse that day by popping it. Then push the meeting's end time. The heap size at the end is the minimum number of days.

Time complexity: \(O(n \log n)\), Space complexity: \(O(n)\)

Pseudo Code

sort(intervals by start);
minHeap = empty min-heap;
for (interval in intervals) {
    if (!minHeap.isEmpty() && minHeap.peek() <= interval.start) {
        minHeap.pop();
    }
    minHeap.push(interval.end);
}
return minHeap.size();