类似题目见博客：https://kirsten-1.github.io/2025/09/08/%E7%AE%97%E6%B3%95%E5%BF%85%E5%A4%87-027-%E5%BF%85%E5%A4%87-%E5%A0%86%E7%BB%93%E6%9E%84%E5%B8%B8%E8%A7%81%E9%A2%98/
提到的线段重合等题目。
方法1:java内置的PriorityQueue实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int minGroups(int[][] intervals) {
int N = intervals.length;
Arrays.sort(intervals, (a, b)->(a[0]-b[0]));
// 用java内置的堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
int ans = 0;
for(int i = 0;i < N;i++) {
while (!heap.isEmpty() && heap.peek() < intervals[i][0]) {
heap.poll();
}
heap.add(intervals[i][1]);
ans = Math.max(ans, heap.size());
}
return ans;
}
}
如果绝对不够快，就用方法2:自己实现小根堆
方法2:自己实现小根堆
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
class Solution {
// 自己写堆
int[] heap;
int size;
public int minGroups(int[][] intervals) {
int N = intervals.length;
int ans = 0;
heap = new int[N];
size = 0;
Arrays.sort(intervals, 0, N, (a, b) -> a[0] - b[0]);
for (int i = 0;i < N;i++) {
if (size > 0 && heap[0] < intervals[i][0]) {
pop();
}
add(intervals[i][1]);
ans = Math.max(ans, size);
}
return ans;
}
public void pop() {
swap(0, --size);
int i = 0, l = 1;
while (l < size) {
int best = l + 1 < size && heap[l + 1] < heap[l] ? l + 1 : l;
best = heap[best] < heap[i] ? best : i;
if (best == i) {
break;
}
swap(best, i);
i = best;
l = 2 * i + 1;
}
}
public void add(int x) {
heap[size] = x;
int i = size++;
while (heap[i] < heap[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
public void swap(int i, int j) {
int t = heap[i];
heap[i] = heap[j];
heap[j] = t;
}
}
