服务器的空闲时段

09 Sep 2024 in Algorithm Pageviews

solve actually problem!

现在有 serverNum 台服务器，编号为 1~serverNum。tasks表示一组任务，tasks[i] = [startTime, endTime, serverId]，依次表示一个任务的开始时刻、结束时刻、服务器编号。任务按照指定的时段在服务器上运行，一台服务器在同一时刻可以并行运行任意多个任务。当一台服务器没有运行任何任务时，称该服务器在该时段空闲，请统计有且仅有一台服务器空闲的时段，并返回排序后的的时段列表(如果没有，返回空列表[])。要求：

• 连续的时段需要合并，如[1, 2]和[2, 3]合并为1, 3
• 按照每个时段的开始时刻进行排序
• 若无法满足要求的时段，则输出空列表

输入：

第一个参数是 serverNum，表示服务器的个数，2 <= serverNum <= 10000

第二个参数是 tasks，1 <= tasks.size() <= 10000

输出：

一个列表，表示排序后的空闲时段，每个元素的格式为: [startTime, endTime]

样例1：

输入：

3

[[1, 2, 1], [1, 3, 1], [5, 6, 1], [2, 3, 2], [5, 6, 3]]

输出：

[[2, 3], [5, 6]]

样例2：

输入：

2

[[1, 3, 1], [1, 2, 2], [2, 3, 2]]

输出：

[]

代码实现如下:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<pair<int, int>> GetFreeTime(int serverNum, const vector<vector<int>> &tasks)
    {
        int usedNum = 0;
        int preTime = 1;
        vector<int> currTasks(serverNum);
        vector<tuple<int, int, int>> points;
        vector<pair<int, int>> res;
        
        for (size_t i = 0; i < tasks.size(); i++) {
            points.push_back(make_tuple(tasks[i][0],  1, tasks[i][2] - 1));
            points.push_back(make_tuple(tasks[i][1], -1, tasks[i][2] - 1));
        }
        
        sort(points.begin(), points.end(), [](const tuple<int, int, int> &a, const tuple<int, int, int> &b) {
            	return make_tuple(get<0>(a)) < make_tuple(get<0>(b));
            });
        
        for (const auto &[pos, val, id] : points) {
            if (pos != preTime) {
                if (usedNum + 1 == serverNum) {
                    res.push_back({preTime, pos});
                    if ((res.size() > 1) &&
                        (res[res.size() - 2].second == res[res.size() - 1].first)) {
                        res[res.size() - 2].second = res[res.size() - 1].second;
                        res.pop_back();
                    }
                }
                preTime = pos;
            }
            
            currTasks[id] += val;
            if ((val == 1) && (currTasks[id] == 1)) {
                usedNum++;
            }
            
            if ((val == -1) && (currTasks[id] == 0)}) {
                usedNum--;
            }
        }
        return res;
    }
};