数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中的旋转门
假设我们有一系列请求，其中requests[i]包含[t, d]，表示在t时刻，一个人到达门口，并想进入（用1表示）或出去（用0表示）。
所以如果只有一个门，并且使用门需要一个时间单位，我们必须遵循一些规则：
门最初处于“进入”状态，然后设置为最后一位参与者使用的状态。
如果在给定时间t只有一个参与者在门口，他们可以使用门。
如果两个或多个参与者想进入，则最早到达的参与者优先，然后先前使用的方向具有优先权。
- 如果没有人使用门一个时间单位，它会恢复到初始状态。
因此，我们必须找到一个排序列表，其中每个元素都包含[t, d]，表示在t时刻，一个人进入或出去。
因此，如果输入类似于[[2,0],[3,1],[6,0],[6,1],[3,0]]，则输出将为[[2,0],[3,0],[4,1],[6,1],[7,0]]
为了解决这个问题，我们将遵循以下步骤：
对数组v进行排序
创建一个列表ret
curr := 1, i := 0, j := 0
n := v的大小
当i < n时，执行：
如果ret不为空且v[i, 0] - ret的最后一个元素的t > 1，则
curr := 1
j := i + 1
定义一个大小为2的数组arr
(将arr[v[i, 1]]加1)
当(j < n且v[j, 0]与v[i, 0]相同)时，执行：
(将arr[v[j, 1]]加1)
t := max((如果ret为空，则为0，否则为ret的最后一个元素的t)和v[i, 0])
如果arr[1]不为零且arr[0]不为零，则：
当arr[curr]不为零时，每步将arr[curr]减一，执行：
将{t, curr}插入到ret的末尾
(将t加1)
curr := curr XOR 1
当arr[curr]不为零时，每步将arr[curr]减一，执行：
将{t, curr}插入到ret的末尾
(将t加1)
否则
curr := v[i, 1]
当arr[curr]不为零时，每步将arr[curr]减一，执行：
将{t, curr}插入到ret的末尾
(将t加1)
curr := ret的最后一个元素的方向
i := j
返回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:
vector<vector<int>> solve(vector<vector<int>>& v) {
sort(v.begin(), v.end());
vector < vector <int > > ret;
int curr = 1;
int i = 0;
int j = 0;
int n = v.size();
while(i < n){
if(!ret.empty() && v[i][0] - ret.back()[0] > 1){
curr = 1;
}
j = i + 1;
vector <int> arr(2);
arr[v[i][1]]++;
while(j < n && v[j][0] == v[i][0]){
arr[v[j][1]]++;
j++;
}
int t = max((ret.empty()? 0 : ret.back()[0] + 1), v[i][0]);
if(arr[1] && arr[0]){
while(arr[curr]--){
ret.push_back({t, curr});
t++;
}
curr = curr ^ 1;
while(arr[curr]--){
ret.push_back({t, curr});
t++;
}
}else{
curr = v[i][1];
while(arr[curr]--){
ret.push_back({t, curr});
t++;
}
}
curr = ret.back()[1];
i = j;
}
return ret;
}
};
int main(){
vector<vector<int>> v = {{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}};
Solution ob;
print_vector(ob.solve(v));
}输入
{{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}}输出
[[2, 0, ],[3, 0, ],[4, 1, ],[6, 1, ],[7, 0, ],]
241 次浏览
