跳转至

2402. 会议室 III

题目描述

给你一个整数 n ,共有编号从 0n - 1n 个会议室。

给你一个二维整数数组 meetings ,其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同

会议将会按以下方式分配给会议室:

  1. 每场会议都会在未占用且编号 最小 的会议室举办。
  2. 如果没有可用的会议室,会议将会延期,直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同
  3. 当会议室处于未占用状态时,将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件,则返回编号 最小 的房间。

半闭区间 [a, b)ab 之间的区间,包括 a 不包括 b

 

示例 1:

输入:n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出:0
解释:
- 在时间 0 ,两个会议室都未占用,第一场会议在会议室 0 举办。
- 在时间 1 ,只有会议室 1 未占用,第二场会议在会议室 1 举办。
- 在时间 2 ,两个会议室都被占用,第三场会议延期举办。
- 在时间 3 ,两个会议室都被占用,第四场会议延期举办。
- 在时间 5 ,会议室 1 的会议结束。第三场会议在会议室 1 举办,时间周期为 [5,10) 。
- 在时间 10 ,两个会议室的会议都结束。第四场会议在会议室 0 举办,时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议,所以返回 0 。 

示例 2:

输入:n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出:1
解释:
- 在时间 1 ,所有三个会议室都未占用,第一场会议在会议室 0 举办。
- 在时间 2 ,会议室 1 和 2 未占用,第二场会议在会议室 1 举办。
- 在时间 3 ,只有会议室 2 未占用,第三场会议在会议室 2 举办。
- 在时间 4 ,所有三个会议室都被占用,第四场会议延期举办。 
- 在时间 5 ,会议室 2 的会议结束。第四场会议在会议室 2 举办,时间周期为 [5,10) 。
- 在时间 6 ,所有三个会议室都被占用,第五场会议延期举办。 
- 在时间 10 ,会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办,时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议,所以返回 1 。 

 

提示:

  • 1 <= n <= 100
  • 1 <= meetings.length <= 105
  • meetings[i].length == 2
  • 0 <= starti < endi <= 5 * 105
  • starti 的所有值 互不相同

解法

方法一:优先队列(小根堆)

我们定义两个优先队列,分别表示空闲会议室、使用中的会议室。其中:空闲会议室 idle 依据下标排序;而使用中的会议室 busy 依据结束时间、下标排序。

先对会议按照开始时间排序,然后遍历会议,对于每个会议:

  • 若有使用中的会议室小于当前等于会议的开始时间,将其加入到空闲会议室队列 idle 中;
  • 若当前有空闲会议室,那么在空闲队列 idle 中取出权重最小的会议室,将其加入使用中的队列 busy 中;
  • 若当前没有空闲会议室,那么在使用队列 busy 中找出最早结束时间且下标最小的会议室,重新加入使用中的队列 busy 中。

时间复杂度 $O(m \times \log m)$,其中 $m$ 为会议数量。

相似题目:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        busy = []
        idle = list(range(n))
        heapify(idle)
        cnt = [0] * n
        for s, e in meetings:
            while busy and busy[0][0] <= s:
                heappush(idle, heappop(busy)[1])
            if idle:
                i = heappop(idle)
                cnt[i] += 1
                heappush(busy, (e, i))
            else:
                a, i = heappop(busy)
                cnt[i] += 1
                heappush(busy, (a + e - s, i))
        ans = 0
        for i, v in enumerate(cnt):
            if cnt[ans] < v:
                ans = i
        return ans
 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
class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> busy
            = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        PriorityQueue<Integer> idle = new PriorityQueue<>();
        for (int i = 0; i < n; ++i) {
            idle.offer(i);
        }
        int[] cnt = new int[n];
        for (var v : meetings) {
            int s = v[0], e = v[1];
            while (!busy.isEmpty() && busy.peek()[0] <= s) {
                idle.offer(busy.poll()[1]);
            }
            int i = 0;
            if (!idle.isEmpty()) {
                i = idle.poll();
                busy.offer(new int[] {e, i});
            } else {
                var x = busy.poll();
                i = x[1];
                busy.offer(new int[] {x[0] + e - s, i});
            }
            ++cnt[i];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (cnt[ans] < cnt[i]) {
                ans = i;
            }
        }
        return ans;
    }
}
 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
using ll = long long;
using pii = pair<ll, int>;

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        priority_queue<int, vector<int>, greater<int>> idle;
        priority_queue<pii, vector<pii>, greater<pii>> busy;
        for (int i = 0; i < n; ++i) idle.push(i);
        vector<int> cnt(n);
        sort(meetings.begin(), meetings.end());
        for (auto& v : meetings) {
            int s = v[0], e = v[1];
            while (!busy.empty() && busy.top().first <= s) {
                idle.push(busy.top().second);
                busy.pop();
            }
            int i = 0;
            if (!idle.empty()) {
                i = idle.top();
                idle.pop();
                busy.push({e, i});
            } else {
                auto x = busy.top();
                busy.pop();
                i = x.second;
                busy.push({x.first + e - s, i});
            }
            ++cnt[i];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (cnt[ans] < cnt[i]) {
                ans = i;
            }
        }
        return ans;
    }
};
 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
42
43
44
45
46
47
48
49
50
51
52
53
54
func mostBooked(n int, meetings [][]int) int {
    sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
    idle := hp{make([]int, n)}
    for i := 0; i < n; i++ {
        idle.IntSlice[i] = i
    }
    busy := hp2{}
    cnt := make([]int, n)
    for _, v := range meetings {
        s, e := v[0], v[1]
        for len(busy) > 0 && busy[0].end <= s {
            heap.Push(&idle, heap.Pop(&busy).(pair).i)
        }
        var i int
        if idle.Len() > 0 {
            i = heap.Pop(&idle).(int)
            heap.Push(&busy, pair{e, i})
        } else {
            x := heap.Pop(&busy).(pair)
            i = x.i
            heap.Push(&busy, pair{x.end + e - s, i})
        }
        cnt[i]++
    }
    ans := 0
    for i, v := range cnt {
        if cnt[ans] < v {
            ans = i
        }
    }
    return ans
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
    a := h.IntSlice
    v := a[len(a)-1]
    h.IntSlice = a[:len(a)-1]
    return v
}

type pair struct{ end, i int }
type hp2 []pair

func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool {
    a, b := h[i], h[j]
    return a.end < b.end || a.end == b.end && a.i < b.i
}
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any)   { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any     { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

评论