TopCoder SRM 645 Div1 Easy: JanuszTheBusinessman (貪欲法)

解法

TopCoder SRM 645 Div1 Easy JanuszTheBusinessman - kmjp's blog

蟻本に載ってた気がする。酷いバグを埋め込んで大変苦労した。

コード

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

public class JanuszTheBusinessman {

	public int makeGuestsReturn(int[] arrivals, int[] departures) {
		int N = arrivals.length;
		boolean[] good = new boolean[N];
		ArrayList<Guest> guests = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			guests.add(new Guest(arrivals[i], departures[i], i));
		}
		Collections.sort(guests);

		int ans = 0;
		for (int q = 0; q < N; q++) {
			if (good[q]) {
				continue;
			}

			int promotionId = -1;
			for (int i = 0; i < N; i++) {
				if (guests.get(i).arrive <= guests.get(q).depart && guests.get(q).depart <= guests.get(i).depart) {
					if (promotionId == -1 || guests.get(promotionId).depart < guests.get(i).depart) {
						promotionId = i;
					}
				}
			}

			for (int i = 0; i < N; i++) {
				if (Math.min(guests.get(promotionId).depart, guests.get(i).depart) >= Math.max(
						guests.get(promotionId).arrive, guests.get(i).arrive)) {
					good[i] = true;
				}
			}
			ans++;

		}

		return ans;
	}

	class Guest implements Comparable<Guest> {
		int arrive, depart, id;

		public Guest(int a, int d, int id) {
			this.arrive = a;
			this.depart = d;
			this.id = id;
		}

		@Override
		public int compareTo(Guest o) {
			return this.depart - o.depart;
		}
	}
}