2007年模擬国内予選〜B問題〜

Osaki-大崎-

心当たりのあるF研関係者は多いと思いますが、やっぱり彼とは関係ありません。
こちらは電車オタの腐女子というよく分からん設定があります。
うまくいくと電車内デートに誘ってくれるとか。
もちろん断るのはあなた次第。

A問題の正しい解法よりも先にこっちの方が思いつく。
ホワイトボードにアルゴリズムを書いてコーダーに投げたけど時刻の比較あたりの実装でいろいろ難儀してた。
結局時間内に解けなかった。
ポイントは発車時刻と到着時刻を持ったクラスを発車順にソートしてリストに保持すること。
あとはシミュレートすれば答えは求まる。

とりあえず分かったことは、Calendarクラスを使うとかCalendarの自力実装とかせずに素直にStringで比較しろということ。
Calendarの比較は遅い。

よってString版

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class B {
	
	Scanner scan = new Scanner(System.in);
	int n;
	
	class Train implements Comparable<Train>{
		String start = "";
		String end = "";
		
		Train(String s, String e){
			start = s;
			end = e;
		}
		
		public int compareTo(Train o) {
			return this.start.compareTo(o.start);
		}
	}
	
	B(){
		for(;;){
			if((n = scan.nextInt()) == 0) break;
			
			ArrayList<Train> list = new ArrayList<Train>();
			for(int i = 0; i < n; i++){
				list.add(new Train(scan.next(), scan.next()));
			}
			Collections.sort(list);
			
			ArrayList<Train> list2 = new ArrayList<Train>();
			for(int i = 0; i < list.size(); i++){
				Train t = list.get(i);
				if(list2.size() == 0){
					list2.add(t);
					continue;
				}
				
				boolean flag = true;
				for(int j = 0; j < list2.size(); j++){
					if(t.start.compareTo(list2.get(j).end) >= 0){
						list2.remove(j);
						list2.add(t);
						flag = false;
						break;
					}
				}
				if(flag){ list2.add(t);	}
			}
			System.out.println(list2.size());
		}	
	}
	
	public static void main(String[] args) {
		new B();
	}
}