มีรายการคำขอ requests โดยแต่ละคำขอเป็น [t, d] หมายถึงเวลา t มีคนมาถึงประตู และต้องการเข้า (d=1) หรือออก (d=0) มีเพียงประตูเดียว ใช้เวลา 1 หน่วยเวลาต่อคน มีกฎดังนี้:
- ประตูเริ่มต้นที่สถานะ "เข้า" (in)
- ถ้ามีคนเพียงคนเดียวที่เวลา
tคนนั้นใช้ประตูได้ทันที - ถ้ามีหลายคนต้องการเข้า คนที่มาก่อนใช้ก่อน แล้วค่อยคำนึงถึงทิศทางที่ใช้ล่าสุด
- ถ้าไม่มีใครใช้ประตูต่อเนื่อง 1 หน่วยเวลา จะกลับสู่สถานะเริ่มต้น (เข้า)
ต้องคืนรายการ [t, d] ที่บอกว่าแต่ละคนใช้ประตูเมื่อไหร่และทิศทางอะไร
ตัวอย่าง
Input: [[2,0],[3,1],[6,0],[6,1],[3,0]]
Output: [[2,0],[3,0],[4,1],[6,1],[7,0]]
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> solve(vector<vector<int>>& v) {
sort(v.begin(), v.end());
vector<vector<int>> ret;
int curr = 1, i = 0, n = v.size();
while(i < n) {
if(!ret.empty() && v[i][0] - ret.back()[0] > 1)
curr = 1;
int j = i + 1;
vector<int> arr(2);
arr[v[i][1]]++;
while(j < n && v[j][0] == v[i][0])
arr[v[j++][1]]++;
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});
curr ^= 1;
while(arr[curr]--) ret.push_back({t++, curr});
} else {
curr = v[i][1];
while(arr[curr]--) ret.push_back({t++, curr});
}
curr = ret.back()[1];
i = j;
}
return ret;
}
};
Input
{{2,0},{3,1},{6,0},{6,1},{3,0}}Output
[[2,0],[3,0],[4,1],[6,1],[7,0]]