ARC 032 C: 仕事計画 (動的計画法)

問題

C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder

解法

ある時刻time以降の仕事の最大数を考える。

コード

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

public class Main {
	private static final int MAX_TIME = 1000001;

	public static void main(String[] args) {
		int N = nextInt();
		int[] ends = new int[N + 1];// 仕事番号に対する終了時刻を記録しておく

		// jobs<start, list>:= startに始まる仕事のリスト
		HashMap<Integer, ArrayList<Interval>> jobs = new HashMap<>();
		for (int i = 0; i < N; i++) {
			int start = nextInt();
			int end = nextInt();
			if (jobs.get(start) == null) {
				jobs.put(start, new ArrayList<Interval>());
			}
			jobs.get(start).add(new Interval(i + 1, end));
			ends[i + 1] = end;

		}

		// dp[time]:= time以降に選択できる仕事の最大数maxと、maxの時の次の仕事番号の最小値
		Pair[] dp = new Pair[MAX_TIME];

		for (int time = MAX_TIME - 1; time >= 0; time--) {
			dp[time] = new Pair(0, Integer.MAX_VALUE);
			if (time == MAX_TIME - 1) {
				// time=MAX_TIME-1の時は後ろに時間&仕事はないのでこのままスルー
				continue;
			} else {
				// 後ろにいる時は直後の情報をコピーしておく
				dp[time].index = dp[time + 1].index;
				dp[time].max = dp[time + 1].max;
			}
			if (jobs.get(time) != null) {
				// timeから始まる仕事が存在する時
				for (Interval job : jobs.get(time)) {
					if (dp[time].max < dp[job.end].max + 1) {
						// jobを取り入れることで最大値を増やせる時
						dp[time].max = dp[job.end].max + 1;
						dp[time].index = job.index;
					} else if (dp[time].max == dp[job.end].max + 1) {
						// 最大値は替わらないが、仕事番号を小さく出来そうな時
						dp[time].index = Math.min(dp[time].index, job.index);
					}
				}
			}
		}

		// 仕事の最大数を出力
		System.out.println(dp[0].max);

		int now = 0;
		while (true) {
			if (dp[now].index > MAX_TIME) {
				break;
			}
			if (now != 0) {
				System.out.print(" ");
			}
			System.out.print(dp[now].index);
			now = ends[dp[now].index];
		}
		System.out.println();

	}

	static class Interval {
		int index, end;

		public Interval(int i, int e) {
			this.index = i;
			this.end = e;
		}
	}

	static class Pair {
		int max, index;

		public Pair(int m, int i) {
			this.max = m;
			this.index = i;
		}
	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}
}