905. 区间选点
摘要
Title: 905. 区间选点
Tag: 区间并集、最大不相交区间数量、贪心
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
905. 区间选点
-
题意
给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。 -
思路
与区间合并不同，这次按照右端点排序一直维护一个区间的右端点，直到新来的区间的左端点大于维护的右端点，说明出现断层，需要新加点；并更新维护的右端点为新区间的右端点，这样是最佳的
同类型题 908. 最大不相交区间数量
-
代码
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'''
Author: NEFU AB-IN
Date: 2022-03-14 17:54:28
FilePath: \ACM\Acwing\905.py
LastEditTime: 2022-03-14 20:47:42
'''
n = int(input())
INF = int(2e9)
r = -INF
a = []
for i in range(n):
L, R = map(int, input().split())
a.append([L, R])
a.sort(lambda x: x[1])
ans = 0
for L, R in a:
if L > r:
ans += 1
r = R
print(ans)
