fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <unordered_map>
  4. using namespace std;
  5.  
  6. class UberShuttle {
  7. private:
  8.     struct Interval {
  9.         int l, r;
  10.  
  11.         Interval(int left, int right) : l(left), r(right) {}
  12.     };
  13.  
  14.     int n;
  15.  
  16.     // l -> r
  17.     unordered_map<int, int> startMap;
  18.  
  19.     // r -> l
  20.     unordered_map<int, int> endMap;
  21.  
  22.     int getSeat(const Interval& interval) {
  23.         int l = interval.l;
  24.         int r = interval.r;
  25.  
  26.         if (l == -1)
  27.             return 0;
  28.  
  29.         if (r == n)
  30.             return n - 1;
  31.  
  32.         return l + (r - l) / 2;
  33.     }
  34.  
  35.     int getDistance(const Interval& interval) {
  36.         int l = interval.l;
  37.         int r = interval.r;
  38.  
  39.         if (l == -1)
  40.             return r;
  41.  
  42.         if (r == n)
  43.             return n - 1 - l;
  44.  
  45.         return (r - l) / 2;
  46.     }
  47.  
  48.     struct Compare {
  49.         UberShuttle* shuttle;
  50.  
  51.         Compare(UberShuttle* s = nullptr) {
  52.             shuttle = s;
  53.         }
  54.  
  55.         bool operator()(const Interval& a,
  56.                         const Interval& b) const {
  57.  
  58.             int distA = shuttle->getDistance(a);
  59.             int distB = shuttle->getDistance(b);
  60.  
  61.             if (distA == distB) {
  62.                 return shuttle->getSeat(a) >
  63.                        shuttle->getSeat(b);
  64.             }
  65.  
  66.             return distA < distB;
  67.         }
  68.     };
  69.  
  70.     priority_queue<
  71.         Interval,
  72.         vector<Interval>,
  73.         Compare
  74.     > pq;
  75.  
  76. public:
  77.     UberShuttle(int seats)
  78.         : n(seats), pq(Compare(this)) {
  79.  
  80.         pq.push(Interval(-1, n));
  81.  
  82.         startMap[-1] = n;
  83.         endMap[n] = -1;
  84.     }
  85.  
  86.     int board() {
  87.  
  88.         while (!pq.empty()) {
  89.  
  90.             Interval curr = pq.top();
  91.             pq.pop();
  92.  
  93.             // Ignore stale intervals
  94.             if (!startMap.count(curr.l) ||
  95.                 startMap[curr.l] != curr.r) {
  96.                 continue;
  97.             }
  98.  
  99.             int seat = getSeat(curr);
  100.  
  101.             startMap.erase(curr.l);
  102.             endMap.erase(curr.r);
  103.  
  104.             Interval left(curr.l, seat);
  105.             Interval right(seat, curr.r);
  106.  
  107.             pq.push(left);
  108.             pq.push(right);
  109.  
  110.             startMap[left.l] = left.r;
  111.             endMap[left.r] = left.l;
  112.  
  113.             startMap[right.l] = right.r;
  114.             endMap[right.r] = right.l;
  115.  
  116.             return seat;
  117.         }
  118.  
  119.         return -1;
  120.     }
  121.  
  122.     void dropOff(int p) {
  123.  
  124.         int left = endMap[p];
  125.         int right = startMap[p];
  126.  
  127.         startMap.erase(p);
  128.         endMap.erase(p);
  129.  
  130.         Interval merged(left, right);
  131.  
  132.         startMap[left] = right;
  133.         endMap[right] = left;
  134.  
  135.         pq.push(merged);
  136.     }
  137. };
  138.  
  139. int main() {
  140.  
  141.     UberShuttle shuttle(10);
  142.  
  143.     cout << shuttle.board() << endl; // 0
  144.     cout << shuttle.board() << endl; // 9
  145.     cout << shuttle.board() << endl; // 4
  146.     cout << shuttle.board() << endl; // 2
  147.  
  148.     shuttle.dropOff(4);
  149.  
  150.     cout << shuttle.board() << endl; // 5
  151.  
  152.     return 0;
  153. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
9
4
2
5
https://ideone.com/tmZvbg
language:
C++ (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!