ICPC 模擬国内予選2007B 大崎 AOJ 2013

まず到着時間が早いもの順にソートする。

それぞれの時間をソートした順にみていき、その時間に運行できる電車があればそのなかで一番最後に到着するものを採用し、なければ新しく電車を使う。

電車の合計数が答え。

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> P;


int times[10010][2];
int train[10010];

int main(){
		int n;
		while(true){
				vector<pair<int,int> > times;
				cin >> n;
				if(n == 0)break;
				for(int i = 0;i < n;i++){
						int a1,a2,a3,b1,b2,b3;
						scanf("%d:%d:%d %d:%d:%d",&a1,&a2,&a3,&b1,&b2,&b3);
						int a = a3 + a2*100 + a1*10000,b = b3 + b2*100 + b1*10000;
						times.push_back(P(b,a));
				}
				sort(times.begin(),times.end());
				vector<int> train;
				train.push_back(0);
				for(int i = 0;i < n;i++){
						int ban=-1,mintime = 1000000;
						for(int j = 0;j < train.size();j++){
								int diff = times[i].second - train[j];
								if(diff >= 0 && diff < mintime){
										mintime = diff;
										ban = j;
								}
						}
						if(ban == -1){
								train.push_back(times[i].first);
						}else{
								train[ban] = times[i].first;
						}
				}
				cout << train.size() << endl;
		}
}