ABC080: D - Recording

問題

D - Recording

解説

同じチャンネルで同一時刻に放送しないので、別々のチャンネルで重なり合う線分の数の最大値が答えとなる。 時刻が整数で[tex:10⁵]以下あることに着目すれば、いもす法で解くのが楽だと分かる。

サンプルを見ながら条件を確認すると楽。同じチャンネルで連続して放映している場合は、先に区間をつなげてしまうと考えやすいと思う。 簡単に区間をつなげるために、チャンネルごとにセグメントを持って時刻でソートした。

区間系の典型的な問題というのもあるが、400点にしては簡単な印象。

int main() {
    int N, C; cin >> N >> C;
    vector<deque<pair<int, int>>> vs(C);
    for (int i=0; i<N; i++) {
        int s, t, c; cin >> s >> t >> c;
        c--;
        vs[c].emplace_back(s, t);
    }

    for (int i = 0; i < C; i++) {
        sort(vs[i].begin(), vs[i].end());
    }

    for (int i = 0; i < C; i++) {
        if (vs[i].empty()) continue;
        deque<pair<int, int>> nv;
        nv.push_back(vs[i][0]);
        for (int j = 1; j < (int)vs[i].size(); j++) {
            if (nv.back().second == vs[i][j].first) {
                auto e = nv.back();
                nv.pop_back();
                e.second = vs[i][j].second;
                nv.push_back(e);
            } else {
                nv.push_back(vs[i][j]);
            }
        }
        vs[i] = nv;
    }

    vector<int> line(100001);
    for (auto channel: vs) {
        for (auto p: channel) {
            for (int i = p.first; i <= p.second; i++) {
                line[i]++;
            }
        }
    }
    cout << *max_element(line.begin(), line.end()) << "\n";
}