AtCoder BeginnerContest 014 C
解説
いもす法。
まず一次元で状態が変わる点をイベントとしてみて、カウンタ +1, -1 の増減を設定する。O(N)
累積和を取り、実際の状態の遷移状況を求める。O(N)
よって全体で O(N)
#include <bits/stdc++.h> using namespace std; #define MAX (1000000) int imos[MAX+10]; int main() { int N; cin >> N; for(int i=0; i<N; i++) { int a, b; cin >> a >> b; imos[a] ++; imos[b+1] --; } for(int i=0; i<MAX; i++) { imos[i+1] += imos[i]; } int mx = 0; for(int i=0; i<=MAX; i++) { if(mx < imos[i]) { mx = imos[i]; } } cout << mx << endl; return 0; }