ABC080D

問題

D - Recording

解法

解説の解法に感動させられたが、自分なりの解法を残しておく。

まず、チャンネル毎に開始時間の早い番組から順に見ていき、同じチャンネルの連続した番組を一つの番組としてまとめる。
この操作を行う事で、全ての番組において、同じ録画機を使うには前の番組の終了時間より開始時間の方が真に遅くなければならなくなる。

あとは、開始時間が早い番組から、使用可能になる時間が一番早い録画機で録画をするようにすれば良い。
もし、一番早い録画機でも録画できない場合は、録画機を増やすことになる。
この操作は、各録画機の使用可能になる時間を優先度付きキューで管理することで、簡単に実装することができる。

計算量は、各操作共にであるため、問題ない。

コード

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;

int main() {
  int N, C; cin >> N >> C;
  vector<priority_queue<P, vector<P>, greater<P>>> p(C);
  for (int i = 0; i < N; i++) {
    int s, t, c; cin >> s >> t >> c;
    p[c-1].push(P(s, t));
  }

  auto comp = [](P a, P b) { return a.first > b.first; };
  priority_queue<P, vector<P>, decltype(comp)> que(comp);
  for (int i = 0; i < C; i++) {
    if (p[i].empty()) continue;
    P time = p[i].top(); p[i].pop();
    while (!p[i].empty()) {
      if (time.second == p[i].top().first) {
        time.second = p[i].top().second; p[i].pop();
      }
      else {
        que.push(time);
        time = p[i].top(); p[i].pop();
      }
    }
    que.push(time);
  }

  priority_queue<int, vector<int>, greater<int>> rec;
  rec.push(que.top().second); que.pop();
  while (!que.empty()) {
    if (rec.top() < que.top().first) rec.pop();
    rec.push(que.top().second); que.pop();
  }
  cout << rec.size() << endl;
}

感想

問題を見たときに、区間スケジューリング問題だと思い込んでしまったため、苦戦した。思い込みは良くない。

楽しくなって優先度付きキューを多用してしまったが、素直にソートした方がわかりやすい気がする。楽しいから止めるつもりはない。