Powered by:NEFU AB-IN

Link

803. 区间合并

• 题意

  给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
  注意如果在端点处相交，也算有交集。
  输出合并完成后的区间个数。
  例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

• 思路

  板子题

  • 别忘了加最后那个区间
  • 统计区间时记得换起点和终点

• 代码

'''
Author: NEFU AB-IN
Date: 2022-02-09 09:44:52
FilePath: \ACM\Acwing\803.py
LastEditTime: 2022-02-09 09:47:55
'''

a = []
INF = int(2e9)

if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        a.append(list(map(int, input().split())))
    a.sort()
    res = 0

    st, ed = -INF, -INF
    for i in range(n):
        if ed < a[i][0]:
            if st != -INF and ed != -INF:
                res += 1
            st = a[i][0]
            ed = a[i][1]
        else:
            ed = max(ed, a[i][1])
    if st != -INF and ed != -INF:
        res += 1
    print(res)