题目描述
给定 N个闭区间 [ai,bi]请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。
输出最小组数。
样例
输入
3
-1 1
2 4
3 5
输出
2
算法1
(贪心) $O(nlogn)$
- 按照区间左端点排序
- 建立小根堆,每次和堆顶元素的右端点(也就是最小的右边界)进行比较,若合法,则作为一组,但要更新右端点,若不合法,则新作为一组。
时间复杂度 $O(nlogn)$
- 排序$O(nlogn)$
- 一层循环内,涉及访问堆顶,元素入堆,和堆顶元素出堆三种操作,访问堆顶$O(1)$,后两种都是$O(logn)$,
而这里的n是指堆元素的数量,从0最多变化到n,因此粗略计算是$O(nlogn)$
那么总的时间复杂度就是$O(nlogn)$
Python 代码
import heapq
n = int(input())
my_range = []
for i in range(n):
l, r = map(int, input().strip().split())
my_range.append([l, r])
if __name__ == "__main__":
# 对原数组按区间左端点排序
my_range.sort(lambda x: x[0])
min_heap = []
for i in range(n):
# 如果冲突,则该区间另开一组
if not min_heap or min_heap[0] >= my_range[i][0]:
heapq.heappush(min_heap, my_range[i][1])
# 如果没有冲突,则更新该组右端点
else:
heapq.heappop(min_heap)
heapq.heappush(min_heap, my_range[i][1])
print(len(min_heap))