【AOJ 2013】Osaki - 日々精進

問題

方針

与えられた時刻はすべて秒に変換する.
pair<int, int>のfirstを時間, secondを出発するときは1, 到着したときは-1として保持
時刻順にソートする.
0～vec.size()まで調べ, 出発したときはカウンタを1, 到着したときは-1していきその最大値が答えになる.

コード

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
 
bool flag[90000];
 
typedef pair<int, int> P;
 
signed main(){ 
  int n;
  int h, m, s;
 
  while(scanf("%d", &n), n){
    fill(flag, flag+90000, false);
    vector<pair<int, int> > time;    
    rep(i, n){
      scanf("%d:%d:%d", &h, &m, &s);
      int start = h * 3600 + m * 60 + s;
      time.pb(P(start, 1));
      scanf("%d:%d:%d", &h, &m, &s);
      int end = h * 3600 + m * 60 + s;
      time.pb(P(end, -1));
    }
     
    sort(time.begin(), time.end());
 
    int cnt = 0;
    int _max = 0;
    rep(i, time.size()){
      if(time[i].second == 1){
        cnt++;
      }else{
        cnt--;
      }
      _max = max(cnt, _max);
    }
 
    cout << _max << endl;
  }
   
  return 0;
}

あとから調べてみたら「いもす法」というらしい（無知）

rep(i, time.size()){
  if(time[i].second == 1){
    cnt++;
  }else{
    cnt--;
  }
  _max = max(cnt, _max);
}

の部分は

rep(i, time.size()){
  cnt += time[i].second;
  _max = max(cnt, _max);
}

でいいというのは書き終わってから他のコードを見ることでわかった.

参考

https://imoz.jp/algorithms/imos_method.html