ประตูหมุนใน C++

สมมติว่าเรามีรายการคำขอ โดยที่คำขอ[i]มี [t, d] ระบุเมื่อถึงเวลา t มีคนมาถึงประตูและต้องการเข้าไปข้างใน (ข้างในแสดงโดยใช้ 1) หรือออกไปข้างนอก (ข้างนอกแสดงว่า โดยใช้ 0).

ดังนั้น หากมีประตูเพียงบานเดียวและต้องใช้หน่วยเวลาในการใช้ประตู มีกฎสองสามข้อที่เราต้องปฏิบัติตาม –

• ประตูเริ่มต้นด้วยตำแหน่ง 'in' จากนั้นจึงตั้งค่าเป็นตำแหน่งที่ผู้เข้าร่วมคนสุดท้ายใช้

• หากมีผู้เข้าร่วมเพียงคนเดียวที่ประตูในเวลาที่กำหนด พวกเขาสามารถใช้ประตูได้

• หากผู้เข้าร่วมตั้งแต่สองคนขึ้นไปต้องการเข้าไป ผู้เข้าร่วมที่เร็วสุดไปก่อนแล้วทิศทางที่ใช้ก่อนหน้านี้จะมีความสำคัญเหนือกว่า

• ถ้าไม่มีใครใช้ประตูสำหรับยูนิตแบบใช้ครั้งเดียว ประตูจะกลับเป็นสถานะเริ่มต้น

ดังนั้น เราต้องหารายชื่อที่จัดเรียงซึ่งแต่ละองค์ประกอบมี [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

• สกุลเงิน :=1, ผม :=0, j :=0

• n :=ขนาดของวี

• ในขณะที่ฉัน

  • ถ้า ret ไม่ว่างเปล่าและ v[i, 0] - t ขององค์ประกอบสุดท้ายของ ret> 1 แล้ว:

    • สกุลเงิน :=1

  • เจ :=ผม + 1

  • กำหนดอาร์เรย์ขนาด 2

  • (เพิ่ม arr[v[i, 1]] โดย 1)

  • ในขณะที่ (j

    • (เพิ่ม arr[v[j, 1]] โดย 1)

  • t :=สูงสุดของ (ถ้า ret ว่างเปล่า แล้ว 0, มิฉะนั้น t ขององค์ประกอบสุดท้ายของ ret) และ v[i, 0]

  • ถ้า arr[1] ไม่ใช่ศูนย์ และ arr[0] ไม่ใช่ศูนย์ ดังนั้น −

    • ในขณะที่ arr[curr] ไม่ใช่ศูนย์ ให้ลด arr[curr] ทีละขั้นในแต่ละขั้นตอน ทำ -

      • ใส่ {t,curr} ที่ส่วนท้ายของ ret

      • (เพิ่มขึ้น t โดย 1)

    • สกุลเงิน :=สกุลเงิน 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

  • ผม :=เจ

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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, ],]