Giả sử chúng ta có một danh sách các yêu cầu, trong đó các yêu cầu [i] chứa [t, d] cho biết tại thời điểm t, một người đã đến cửa và muốn vào trong (bên trong biểu thị bằng 1) hoặc đi ra ngoài (bên ngoài cho biết sử dụng 0).
Vì vậy, nếu chỉ có một cửa và phải sử dụng một đơn vị thời gian thì chúng ta phải tuân theo một số quy tắc -
-
Cánh cửa bắt đầu với vị trí 'in' và sau đó được đặt thành vị trí được sử dụng bởi người tham gia cuối cùng.
-
Nếu chỉ có một người tham gia ở cửa vào thời điểm t nhất định, họ có thể sử dụng cửa.
-
Nếu hai hoặc nhiều người tham gia muốn vào, người tham gia sớm nhất đi trước và hướng được sử dụng trước đó được ưu tiên.
- Nếu không có ai sử dụng cửa cho thiết bị dùng một lần, cửa sẽ trở lại trạng thái ban đầu.
Vì vậy, chúng ta phải tìm danh sách đã sắp xếp trong đó mỗi phần tử chứa [t, d], cho biết tại thời điểm t, một người đã đi vào bên trong hoặc bên ngoài.
Vì vậy, nếu đầu vào là [[2,0], [3,1], [6,0], [6,1], [3,0]], thì đầu ra sẽ là [[2,0] , [3,0], [4,1], [6,1], [7,0]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp mảng v
-
tạo một danh sách ret
-
curr:=1, i:=0, j:=0
-
n:=kích thước của v
-
trong khi tôi
-
nếu ret không trống và v [i, 0] - t của phần tử cuối cùng của ret> 1, thì:
-
curr:=1
-
-
j:=i + 1
-
Xác định arr mảng có kích thước 2
-
(tăng arr [v [i, 1]] lên 1)
-
while (j
-
(tăng arr [v [j, 1]] lên 1)
-
-
t:=Maximum of (nếu ret trống thì 0, nếu không t thuộc phần tử cuối cùng của ret) và v [i, 0]
-
nếu arr [1] khác 0 và arr [0] khác 0 thì -
-
trong khi arr [curr] khác 0, hãy giảm arr [curr] xuống một trong mỗi bước, thực hiện -
-
chèn {t, curr} vào cuối ret
-
(tăng t lên 1)
-
-
curr:=curr XOR 1
-
trong khi arr [curr] khác 0, hãy giảm arr [curr] xuống một trong mỗi bước, thực hiện -
-
chèn {t, curr} vào cuối ret
-
(tăng t lên 1)
-
-
-
Nếu không
-
curr:=v [i, 1]
-
trong khi arr [curr] khác 0, hãy giảm arr [curr] xuống một trong mỗi bước, thực hiện -
-
chèn {t, curr} vào cuối ret
-
(tăng t lên 1)
-
-
-
curr:=hướng của phần tử cuối cùng của ret
-
i:=j
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}} Đầu ra
[[2, 0, ],[3, 0, ],[4, 1, ],[6, 1, ],[7, 0, ],]