
题目描述
给你一个数组 events
,其中 events[i] = [startDayi, endDayi]
,表示会议 i
开始于 startDayi
,结束于 endDayi
。
你可以在满足 startDayi <= d <= endDayi
中的任意一天 d
参加会议 i
。在任意一天 d
中只能参加一场会议。
请你返回你可以参加的 最大 会议数目。
示例 1:

输入:events = [[1,2],[2,3],[3,4]]
输出:3
解释:你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
示例 2:
输入:events= [[1,2],[2,3],[3,4],[1,2]]
输出:4
提示:
1 <= events.length <= 105
events[i].length == 2
1 <= startDayi <= endDayi <= 105
解法
方法一:哈希表 + 贪心 + 优先队列
我们用一个哈希表 \(\textit{g}\) 记录每个会议的开始和结束时间。键为会议的开始时间,值为一个列表,包含所有在该开始时间开始的会议的结束时间。用两个变量 \(\textit{l}\) 和 \(\textit{r}\) 分别记录会议的最小开始时间和最大结束时间。
对于从小到大每个在 \(\textit{l}\) 到 \(\textit{r}\) 的时间点 \(s\),我们需要做以下操作:
- 从优先队列中移除所有结束时间小于当前时间 \(s\) 的会议。
- 将所有开始时间等于当前时间 \(s\) 的会议的结束时间加入优先队列中。
- 如果优先队列不为空,则取出结束时间最小的会议,累加答案数,并从优先队列中移除该会议。
这样,我们可以确保在每个时间点 \(s\),我们都能参加结束时间最早的会议,从而最大化参加的会议数。
时间复杂度 \(O(M \times \log n)\),空间复杂度 \(O(n)\),其中 \(M\) 和 \(n\) 分别为会议的最大结束时间和会议的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
g = defaultdict(list)
l, r = inf, 0
for s, e in events:
g[s].append(e)
l = min(l, s)
r = max(r, e)
pq = []
ans = 0
for s in range(l, r + 1):
while pq and pq[0] < s:
heappop(pq)
for e in g[s]:
heappush(pq, e)
if pq:
heappop(pq)
ans += 1
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 | class Solution {
public int maxEvents(int[][] events) {
Map<Integer, List<Integer>> g = new HashMap<>();
int l = Integer.MAX_VALUE, r = 0;
for (int[] event : events) {
int s = event[0], e = event[1];
g.computeIfAbsent(s, k -> new ArrayList<>()).add(e);
l = Math.min(l, s);
r = Math.max(r, e);
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
int ans = 0;
for (int s = l; s <= r; s++) {
while (!pq.isEmpty() && pq.peek() < s) {
pq.poll();
}
for (int e : g.getOrDefault(s, List.of())) {
pq.offer(e);
}
if (!pq.isEmpty()) {
pq.poll();
ans++;
}
}
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 | class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
unordered_map<int, vector<int>> g;
int l = INT_MAX, r = 0;
for (auto& event : events) {
int s = event[0], e = event[1];
g[s].push_back(e);
l = min(l, s);
r = max(r, e);
}
priority_queue<int, vector<int>, greater<int>> pq;
int ans = 0;
for (int s = l; s <= r; ++s) {
while (!pq.empty() && pq.top() < s) {
pq.pop();
}
for (int e : g[s]) {
pq.push(e);
}
if (!pq.empty()) {
pq.pop();
++ans;
}
}
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 | func maxEvents(events [][]int) (ans int) {
g := map[int][]int{}
l, r := math.MaxInt32, 0
for _, event := range events {
s, e := event[0], event[1]
g[s] = append(g[s], e)
l = min(l, s)
r = max(r, e)
}
pq := &hp{}
heap.Init(pq)
for s := l; s <= r; s++ {
for pq.Len() > 0 && pq.IntSlice[0] < s {
heap.Pop(pq)
}
for _, e := range g[s] {
heap.Push(pq, e)
}
if pq.Len() > 0 {
heap.Pop(pq)
ans++
}
}
return
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
n := len(h.IntSlice)
v := h.IntSlice[n-1]
h.IntSlice = h.IntSlice[:n-1]
return v
}
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
|
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 | function maxEvents(events: number[][]): number {
const g: Map<number, number[]> = new Map();
let l = Infinity,
r = 0;
for (const [s, e] of events) {
if (!g.has(s)) g.set(s, []);
g.get(s)!.push(e);
l = Math.min(l, s);
r = Math.max(r, e);
}
const pq = new MinPriorityQueue<number>();
let ans = 0;
for (let s = l; s <= r; s++) {
while (!pq.isEmpty() && pq.front() < s) {
pq.dequeue();
}
for (const e of g.get(s) || []) {
pq.enqueue(e);
}
if (!pq.isEmpty()) {
pq.dequeue();
ans++;
}
}
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 | use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;
impl Solution {
pub fn max_events(events: Vec<Vec<i32>>) -> i32 {
let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
let mut l = i32::MAX;
let mut r = 0;
for event in events {
let s = event[0];
let e = event[1];
g.entry(s).or_default().push(e);
l = l.min(s);
r = r.max(e);
}
let mut pq = BinaryHeap::new();
let mut ans = 0;
for s in l..=r {
while let Some(&Reverse(top)) = pq.peek() {
if top < s {
pq.pop();
} else {
break;
}
}
if let Some(ends) = g.get(&s) {
for &e in ends {
pq.push(Reverse(e));
}
}
if pq.pop().is_some() {
ans += 1;
}
}
ans
}
}
|