今日头条试题:小明在抖音关注了n个主播,每个主播每天的开播时间是固定的,分别在时刻开始,ti时刻结束


作者:喵咪咪
链接:https://www.nowcoder.com/discuss/93459?type=0&order=0&pos=23&page=0
来源:牛客网

5. 小明在抖音关注了n个主播,每个主播每天的开播时间是固定的,分别在时刻开始,ti时刻结束。小明无法同时看两个直播。一天被分为m个时间单位。请问小明每天最多能完整观看多少个直播?
输入描述:
第一行一个整数,代表n
第二行一个整数,代表m
第三行空格分隔n*2个整数,代表s,t
输出描述:
一行一个整数,表示答案
输入:
3 
10
0 3 3 7 7 0
输出
3
数据范围:
1 <= n <= 10^5
2 <= m <= 10^6
0 <= si,ti < m
class Solution:
    def __init__(self):
        pass

    def conflict(self, state, next_tuple):
        if not state:
            return False
        if not next_tuple:
            return True
        for i in range(len(state)):
            if (next_tuple[0] <= state[i][0] and next_tuple[1] > state[i][0]) or (next_tuple[0] >= state[i][0] and next_tuple[0] < state[i][1]):
                return True
        return False

    def find_method(self, lst, array):
        if not lst:
            return array
        array.append([lst[0]])
        length = len(array)
        for i in range(length):
            if not self.conflict(array[i], lst[0]):
                arr = array[i][:]
                arr.append(lst[0])
                array.append(arr)
        self.find_method(lst[1:], array)
        return array

    def find_max(self, array):
        max = 0
        lst = []
        #print("length of array= %d" % len(array))
        for i in range(len(array)):
            length = len(array[i])
            if length > max:
                max = length
                lst = array[i]
        print(max)
        print(lst)

if __name__ == "__main__":
    '''
    array contain all alternative result
    '''
    so = Solution()
    lst = [[0, 3], [3, 7], [7, 10]]
    array = []
    so.find_method(lst, array)
    so.find_max(array)