4100.md

进程监测 4100: 进程检测

题目要求用最少的检测次数来检测进程。

题目来源

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

可以采用贪心的策略，首先统计全部进程占用的时间点，通过桶的方式把每个时间点重叠进程也记录下来。 然后把重叠次数最多的点提取出来累加一次，然后排除掉所有与该时间点有重合的进程，之后重复此过程得到统计结果即可。

#include <iostream>
#include <vector>
using namespace std;
struct proc {
	int s;
	int d;
};
int main() {
	int k, i, n, j, s;
	cin >> k;
	for (i = 0; i < k; ++i) {
		cin >> n;
		int data[101] = { 0 }, amount = 0;
		vector<proc> vp;
		for (j = 0; j < n; ++j) {
			proc pr;
			cin >> pr.s >> pr.d;
			vp.push_back(pr);
			for (s = pr.s; s <= pr.d; ++s) {
				data[s]++;
			}
		}
		while (vp.size() > 0) {
			int mp = 0, mIdx = 0;
			for (j = 0; j < 101; ++j) {
				if (mp < data[j]) {
					mp = data[j];
					mIdx = j;
				}
			}
			amount++;
			for (j = 0; j < vp.size(); ++j) {
				if (vp[j].s <= mIdx && vp[j].d >= mIdx) {
					for (s = vp[j].s; s <= vp[j].d; ++s) {
						data[s]--;
					}
					vp.erase(vp.begin() + j--);
				}
			}
		}
		cout << amount << endl;
	}
	return 0;
}

4100.cpp 代码长度：781B 内存：136kB 时间：3ms 通过率：74% 最小内存：136kB 最短时间：0ms

桶可以采用数组来存储，对于进程可以构造结构体来存储，对于进程数组可以考虑使用vector来处理以方便删除。

有任何的改进意见欢迎大家在微信平台公众号主页面留言或者发表issue。