华为OD机试真题- 任务混部

题目描述: 公司创新实验室正在研究如何最小化资源成本，最大化资源利用率，请你设计算法帮他们解决一个任务混部问题:有taskNum项任务，每个任务有开始时间(startTime )，结束时间（endTime)，并行度(parallelism)三个属性，并行度是指这个任务运行时将会占用的服务器数量，一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用，任务运行完会立即释放（结束时刻不占用)。任务混部问题是指给定一批任务，让这批任务由同一批服务器承载运行，请你计算完成这批任务混部最少需要多少服务器，从而最大化控制资源成本。 输入描述: 第一行输入为taskNum，表示有taskNum项任务 接下来taskNum行，每行三个整数，表示每个任务的开始时间(startTime )，结束时间(endTime)，并行度(parallelism) 输出描述: 一个整数，表示最少需要的服务器数量

补充说明: 1<=taskNum<=100000 <=startTime<endTime<=500001=<parallelism<=100

示例1 输入: 3 2 3 1 6 9 2 0 5 1 输出: 2

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
	int task_num;
	cin >> task_num;

	vector<vector<int>> ranges;
	for (int i = 0; i < task_num; i++) {
		int start, end, value;
		cin >> start >> end >> value;
		ranges.push_back({ start, end, value });
	}

	sort(ranges.begin(), ranges.end());//按区间左端点从小到大排序

	// 定义小根堆，存储已经考虑过但未被完全包含的区间，按右端点从小到大排序
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;//end,value
	int res = 0, temp_res = 0;
	for (int i = 0; i < ranges.size(); i++) {
		while (!pq.empty()) {
			auto top = pq.top();

			if (top.first < ranges[i][0]) {
				// 当前正在考虑的区间集合与堆顶区间不相交，则弹出堆顶区间
				pq.pop();
				temp_res -= top.second;
			}
			else {
				break;
			}
		}

		pq.push(make_pair(ranges[i][1], ranges[i][2]));
		temp_res += ranges[i][2];

		if (temp_res > res) {
			res = temp_res;
		}
	}

	cout << res << endl;

	return 0;
}