2021-07-30 最多不重叠区间数量

题目描述：你今天有好几个活动，每个活动都可以用区间[start, end]来表示开始和结束的时间，请问今天最多能参加几个活动？

# -*- utf-8 -*- #

import sys


"""
输入：[["10:00", "12:00"], ["03:00", "11:30"],
 ["11:30", "14:00"]]
输出：至多参加的社团的数量
"""
# 参考：https://linbo-lin.github.io/2020/03/17/Python%E4%B8%ADsort-sorted%E8%87%AA%E5%AE%9A%E4%B9%89%E6%8E%92%E5%BA%8F%E8%A7%84%E5%88%99/
# lines = []
# for line in sys.stdin:
#     line = line.strip()
#     lines.append(line)


inputCMD = [["10:00", "12:00"], ["03:00", "11:30"], ["11:30", "14:00"]]
inputCMD = [[int(j[:2])*60+int(j[3:]) for j in i] for i in inputCMD]
print(inputCMD)


def interval_schedule(intvs):
    class Compare(list):
        def __lt__(self, num):
            return self[1] < num[1]
    if len(intvs) == 0:
        return 0
    ret = sorted([e for e in intvs], key=Compare)
    # return ret
    # 至少有一个区间不相交
    cnt = 1
    # 排序后，第一个区间就是x
    xEnd = ret[0][1]
    for i in intvs:
        start = i[0]
        if start >= xEnd:
            # 找到一个合适区间
            cnt += 1
    return cnt


ret = interval_schedule(inputCMD)
print(ret)