python-线段和点

解题思路:

这道题的题意不太好理解。

这里先解释一下，题目的要求就是最少几个点，可以使得题目所给的区间都被满足。

那题目给的例子来说：

点集：2，6，3，8，7
集合：2 5，3 4，3 3，2 7，6 9

点2能满足的区间为：2 5，2 7                     点6能满足的区间为：2 7，6 9

点3能满足的区间为：2 5，3 4，3 3，2 7    点8能满足的区间为：6 9  

点7能满足的区间为：2 7，6 9

想要满足所有的区间，我们可以取点①3，6 ②3，8 ③3，7  最少要取两个点，所以输出的结果是2

解题方法：

①用A表示点集，将点集从小到大排序。用B表示区间，将区间根据左端点从小到大排序，左端点相同的根据右端点从大到小排序。

②用变量ans表示所选择的点的个数。用变量start表示当前选择的ans个点已经满足到第start个区间（目的是要满足所有区间）

③每次从点集A中寻找到可以将start变得最大的点（也就是使得start最靠近m的点）  ，找到之后将start更新到当前区间，ans+1，将这个点从A中删除。

   如果start < m，再次从点集A中寻找到可以将start变得最大的点，重复第③步，如果A中剩余的点为0，跳出循环。

注意事项:

参考代码:

def f(n,m):    
    A = [0 for i in range(n)]    
    for i in range(n):    
        A[i] = int(input())    
    A.sort()       #A点集排序    
    B = [[0,0] for i in range(m)]    
    for i in range(m):    
        B[i][0],B[i][1] = map(int,input().strip().split())    
    B = sorted(B,key = lambda x:(x[0],-x[1]))  #B区间排序    
      
    start = 0  #定位推进区间    
    ans = 0    
    while start < m:    
        max_num = 0    
        max_index = 0    
        for i in range(len(A)):   #寻找使得start最接近m的点    
            temp = start    
            while temp < m:    
                if B[temp][0]<= A[i] <= B[temp][1]:    
                    temp = temp + 1    
                else:    
                    break    
            if temp > max_num:   #记录该点的下标和区间    
                max_num = temp    
                max_index = i    
        start = max_num    #更新start    
        del(A[max_index])  #删除该点    
        ans = ans + 1    
        if len(A) == 0:    
            break    
      
    if start == m:    
        print(ans)    
    else:    
        print(-1)    
                      
                             
if __name__ == '__main__':      
    n,m = map(int,input().strip().split())      
    f(n,m)