TechFUL: マスクが買いたい

TechFUL TechFUL: 中級 いもす法

問題概要

Tech ちゃんはお店に買い物にいく．

お店は時刻 0 ちょうどに開き、時刻 E ちょうどに閉まる．

N 人のお客さんの出入りのデータが与えられる．

i 番目のお客さんは時刻 S_{i} にお店に入り、時刻 T_{i} にお店を出る．

お客さんが最も少ない時間を出力せよ．

制約

  • 0 \lt E \le 2 \times 10^{5}

  • 0 \le N \le 10^{5}

  • 0 \le S_{i} \le T_{i} \le E

解法

各時間帯におけるお客さんの人数をいもす法を用いて求め、お客さんが最も少ない時間帯を列挙する．

いもす法の解説：いもす法 - いもす研 (imos laboratory)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int E, N;
    cin >> E >> N;
    vector<int> cum(E + 1, 0);
    for (int i = 0; i < N; ++i) {
        int S, T;
        cin >> S >> T;
        cum[S]++;
        cum[T]--;
    }
    for (int i = 0; i < E; ++i) {
        cum[i + 1] += cum[i];
    }
    int num = N;
    for (int i = 0; i < E; ++i) {
        num = min(num, cum[i]);
    }
    for (int i = 0; i < E; ++i) {
        if (cum[i] == num) {
            cout << i << " ";
        }
    }
    cout << endl;
}