04100: 进程检测

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

有n个任务进程p1，p2，…，pn，对于任务pi，开始时间是s[i]，截止时间是d[i]。开始时间和截止时间均为非负整数，且不超过100。有一个监测程序Test来测试正在运行的任务进程。Test每次测试的时间很短，可以忽略不计。换句话说，如果Test在时刻t进行测试，那么对于满足s[i]<=t<=d[i]的所有进程pi同时完成测试。要求每个进程pi至少用test完成测试一次。通过合理的安排test程序测试的时间，既可以满足每个进程pi至少用test完成测试一次的要求，又使得test测试的次数最少。给定n个任务进程的起止时间，给出test测试的最少次数。

输入

第一行为k，表示有k组测试输入，k<100。每组第一行为n，表示有n个进程，n<50。接下来n行，每行是用空格隔开的两个非负整数，第i行的分别是第i个进程的起止时间s[i]和d[i]， 1<=i<=n。s[i]和d[i]均可用int类型存下。

输出

对每组测试数据输出一行，每行一个数字是Test程序执行的最少次数。

样例输入

样例输出

1
2

【尹显齐25物院】发现M04100用M16528的代码可以AC。与16528本质一样，16528有end<60约束，4100没有写t的范围，可能数据范围更小。

python

import sys
#from itertools import islice
from collections import namedtuple

# 使用 namedtuple 简化类定义
Pro = namedtuple('Pro', ['s', 'd'])


def main():
    input = sys.stdin.read
    data = input().split()

    k = int(data[0])
    results = []

    index = 1
    for _ in range(k):
        n = int(data[index])
        index += 1

        ex = [Pro(int(data[index + 2 * i]), int(data[index + 2 * i + 1])) for i in range(n)]
        index += 2 * n

        ex.sort(key=lambda x: x.s)

        m = ex[-1].s
        t = 1

        for i in range(n - 2, -1, -1):
            if ex[i].d >= m:
                continue
            else:
                m = ex[i].s
                t += 1

        results.append(t)

    for result in results:
        print(result)


if __name__ == "__main__":
    main()

04100: 进程检测 ​

04100: 进程检测