OpenJudge

4100:进程检测

总时间限制:
1000ms
内存限制:
65536kB
描述

有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程序执行的最少次数。
样例输入
2
2
1 3
2 4
3
1 3
2 3
4 5
样例输出
1
2
全局题号
5584
添加于
2014-12-13
提交次数
435
尝试人数
146
通过人数
114
您的评价 很水 简单 一般 较难 变态
  • 标签(多个标签用空格分隔):
  • 常用标签:
    递归   动态规划   贪心   搜索   枚举   模拟   数学   字符串处理   几何   高精度计算   图论  

共有6人评分

16.7%
0.0%
16.7%
33.3%
33.3%