区間スケジューリング問題

区間スケジューリング問題(プログラミングコンテストチャレンジブック p43)

N個の仕事がある。各仕事は、時間に始まり、時間[t_i]に終わる。仕事に参加するなら、その仕事のはじめから終わりまで参加しなければならない。参加する仕事の時間帯が重なってはいけない。最大何個の仕事に参加できるか。
制約

アルゴリズム

貪欲法

○選べる仕事の中で、終了時間が早いものを選ぶことを繰り返す

他の任意の選び方に対し、この選び方は、開始時間が早いものから同じ個数のところで、終了時間が遅くない。したがって、他に多く選べる選び方はない。

×選べる仕事の中で、開始時間が最も早いものを選ぶことを繰り返す

反例

×選べる仕事の中で、時間が最も短いものを選ぶことを繰り返す

反例

×選べる仕事の中で、その仕事を選んだときに選べなくなる他の仕事の数が最も少ないものを選ぶことを繰り返す

反例

コード

import java.util.*;
import java.lang.*;
public class Interval_Scheduling_Problem {
	static Scanner scanner;
	
	Interval_Scheduling_Problem (){
		int N = scanner.nextInt();
		pair[] job = new pair[N];
		for(int i = 0; i<N; i++){
			int s = scanner.nextInt();
			int t = scanner.nextInt();
			job[i] = new pair(s,t);
		}
		System.out.println( solve(N, job) );
	}
	
	int solve(int N, pair[] job){
		int ans = 0, t = 0; //最後に選んだjobの修了時刻(0<修了時刻, 0<開始時刻)
		Arrays.sort(job); //修了時刻でソート
		for(int i=0; i<N; i++){
			if( t < job[i].s ){ //最後に選んだjobの修了時刻 < 次に選ぶjobの開始時刻
				ans++;
				t = job[i].t;
			}
		}
		return ans;
	}
	
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new Interval_Scheduling_Problem ();
	}

}

class pair implements Comparable{
	int s,t;
	pair(int s, int t){ this.s = s; this.t = t; }
	public int compareTo(Object ob){ return this.t - ((pair)ob).t; }
}