2479. Meeting Rooms III

难度: Hard

题目描述

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.

Meetings are allocated to rooms in the following manner:

1. Each meeting will take place in the unused room with the lowest number.
2. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
3. When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

A half-closed interval [a, b) is the interval between a and b including a and not including b.

 

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0. 

Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1. 

 

Constraints:

• 1 <= n <= 100
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 0 <= starti < endi <= 5 * 105
• All the values of starti are unique.

解题思路

代码实现

解决方案

java

class Solution {
    private class Pair<K, V> {
        public K first;
        public V second;

        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }
    }

    public int mostBooked(int n, int[][] meetings) {
        // 根据开始时间排序
        Arrays.sort(meetings, (x, y) -> x[0] - y[0]);
        // 记录会议室使用次数
        int[] count = new int[n];
        // 可用会议室 ，从小到大排序
        TreeSet<Integer> emptyRoom = new TreeSet<>();
        // 初始化可用会议室
        for (int i = 0; i < n; i++) {
            emptyRoom.add(i);
        }
        // 使用中的会议室 按照会议 优先队列记录 {结束时间，占用的会议室}，优先按照结束时间排序
        PriorityQueue<Pair<Long, Integer>> heap = new PriorityQueue<>(
                (x, y) -> Long.compare(x.first, y.first) == 0 ? x.second - y.second : Long.compare(x.first, y.first));
        for (int[] meeting : meetings) {

            // 如果有结束时间早于当前会议开始时间的可弹出
            while (!heap.isEmpty() && meeting[0] >= heap.peek().first) {
                emptyRoom.add(heap.poll().second);
            }

            if (emptyRoom.isEmpty()) {
                Pair<Long, Integer> cur = heap.poll();
                count[cur.second]++;
                // 延迟时间
                heap.offer(new Pair<>(cur.first + (long) meeting[1] - meeting[0], cur.second));
            } else {
                int get = emptyRoom.first();
                heap.offer(new Pair<>((long) meeting[1], get));
                count[get]++;
                emptyRoom.remove(get);
            }
        }
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (count[max] < count[i])
                max = i;
        }

        return max;

    }
}