T01230:Pass-Muraille

http://cs101.openjudge.cn/practice/01230/

【陈子良 25物理学院】我们在M16528充实的寒假生活中做过这样的题：给定一个区间集合，问最少取出多少个集合，使剩余的区间互不重叠。这题有相当直观的贪心策略：将区间按右端点排序，依次判断当前区间与之前保留的区间是否重叠，如果不重叠则保留。

这道题是加强版，给定一个区间集合，问最少取出多少个集合，使剩余的区间重叠数不超过k次。你猜怎么着？贪心策略和之前几乎完全一样。用一个列表condition存储每个点的重叠数，按区间右端点排序，对于每一个区间，判断如果加上当前区间，前面的点重叠数是否超过k，如果不超过k则保留当前区间。

for _ in range(int(input())):
    n,k=map(int,input().split())
    wall=[]
    for _ in range(n):
        x1,y1,x2,y2=map(int,input().split())
        if x1>x2:
            x1,x2=x2,x1
        wall.append((x1,x2))
    wall.sort(key=lambda x:(x[1],x[0]))
    condition=[0]*101
    s=0
    for t in wall:
        x1,x2=t[0],t[1]
        if all(condition[x]<k for x in range(x1,x2+1)):
            for x in range(x1,x2+1):
                condition[x]+=1
        else:
            s+=1
    print(s)