数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的员工空闲时间
假设我们给定了一个员工日程列表；这表示每个员工的工作时间。现在假设每个员工都有一个不重叠的区间列表，这些区间是有序的。我们必须找到表示所有员工的公共、正长度空闲时间的有限区间列表，并且该列表也按顺序排列。我们以 [x, y] 的形式表示区间，例如，schedule[0][0].start = 1，schedule[0][0].end = 2。
因此，如果输入类似于 schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]，则其中一个输出将是 [[3,4]]。
要解决此问题，我们将遵循以下步骤 -
定义一个二维数组 v
初始化 i := 0，当 i < schedule 的大小，更新（i 增加 1），执行
初始化 j := 0，当 j < schedule[i] 的大小，更新（j 增加 1），执行
将 schedule[i, j] 插入 v 的末尾
对数组 v 进行排序
定义一个二维数组 ret
定义一个数组 temp := v[0]
初始化 i := 0，当 i < v 的大小，更新（i 增加 1），执行 -
如果 temp[0] < v[i, 1]，则 -
将 {temp[1], v[i, 0]} 插入 ret 的末尾
temp := v[i]
否则
temp := (如果 temp[1] < v[i, 1]，则 v[i]，否则 temp)
返回 ret
让我们看看以下实现以获得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
static bool cmp(vector<int> a, vector<int> b){
return a[0] < b[0];
}
vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>> schedule) {
vector<vector<int>> v;
for (int i = 0; i < schedule.size(); i++) {
for (int j = 0; j < schedule[i].size(); j++) {
v.push_back(schedule[i][j]);
}
}
sort(v.begin(), v.end(), cmp);
vector<vector<int>> ret;
vector<int> temp = v[0];
for (int i = 0; i < v.size(); i++) {
if (temp[0] < v[i][1]) {
ret.push_back({temp[1], v[i][0]});
temp = v[i];
} else {
temp = temp[1] < v[i][1] ? v[i] : temp;
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<vector<int>>> v = {{{1,2},{5,6}},{{1,3}},{{4,10}}};
print_vector(ob.employeeFreeTime(v));
}输入
{{{1,2},{5,6}},{{1,3}},{{4,10}}}输出
[[2, 1, ],[2, 1, ],[3, 4, ],[10, 5, ],]
更新于: 2020-07-11
398 次查看
广告