AcWing 906. 区间分组
原题链接
简单
作者:
皓首不倦
,
2020-09-05 21:23:15
,
所有人可见
,
阅读 364
'''
贪心策略
所有区间按照左端点升序排序,然后枚举每一个区间,同时用一个小顶堆维护所有
分组中区间右端点的最大值,每次迭代区间如果能够找到分组放进去就放进去,否则
重新增加一个分组,最后统计分组的总个数即可
'''
from queue import PriorityQueue
n = int(input())
arr = []
for _ in range(n):
a, b = map(int, input().split())
arr.append((a, b))
arr.sort()
que = PriorityQueue()
for start, end in arr:
if que.empty():
que.put(end) # 维护分组中所有区间的右端点最大值
else:
if que.queue[0] < start:
que.get()
que.put(end)
else:
que.put(end)
print(que.qsize())