题解 | 剩下的树

import sys
def remove(total,num,it):
    data=[]
    for _ in range(num):
        tem=list(map(int,next(it).strip('\n').split()))
        data.append(tem)
    data=sorted(data,key=lambda x:x[0])
    right=data[0][1]
    left=data[0][0]
    remove=0
    for i in range(1,num):
        if data[i][0]>right:
            remove+=right-left+1
            left=data[i][0]
            right=data[i][1]
        else:
            right=max(data[i][1],right)
    remove+=right-left+1
    print(total-remove)
if __name__ =='__main__':
    it=iter(sys.stdin)
    while 1:
        try:
            tem=list(map(int,next(it).strip('\n').split()))
            total=tem[0]+1
            num=tem[1]
            remove(total,num,it)
        except:
            break

贪心算法维护重叠子区间的范围并计算移除的树