leetcode-go/poj/3190.stall-reservations/main.cc

#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

struct Cow {
  int i;
  int s;
  int e;
  bool operator<(const Cow &that) const { return this->s < that.s; }
};

struct Stall {
  int i;
  int e;
  // The < op here means the rank of this is LESS than the rank of that.
  bool operator<(const Stall that) const { return this->e > that.e; }
};

const int N = 50000;

int main() {
  int n, res[N];
  Cow c[N];
  while (scanf("%d", &n) != EOF) { // Multi group of input
    for (int i = 0; i < n; i++) {
      scanf("%d %d", &c[i].s, &c[i].e);
      c[i].i = i;
    }
    sort(c, c + n);

    priority_queue<Stall> q;
    int id = 0;
    res[c[0].i] = ++id;
    q.push({id, c[0].e});

    for (int i = 1; i < n; i++) {
      Stall s = q.top();
      if (s.e < c[i].s) { // Is NOT <=, but < only
        res[c[i].i] = s.i;
        s.e = c[i].e;
        q.pop();
      } else {
        res[c[i].i] = ++id;
        s = {id, c[i].e};
      }
      q.push(s);
    }

    printf("%d\n", id);
    for (int i = 0; i < n; i++) printf("%d\n", res[i]);
  }
  return 0;
}