CODE FESTIVAL 2014 Middle B: 枕決め

問題

B: 枕決め - CODE FESTIVAL 2014 Middle | AtCoder

解法

• 高さhを1から少しずつ大きくしていく。
• x[i]=hになる人iがいたら、y[i]をPriorityQueueに入れる。
• PriorityQueueの中でy
• hの高さの枕をPriorityQueueの人に順番に配る。

ジョブスケジューリング（イメージ）っぽい。

コード

import java.io.IOException;
import java.util.PriorityQueue;

public class Main {
	private static final int MAX_H = 100000;

	public static void main(String[] args) {
		int N = nextInt();
		int M = nextInt();
		int[] y = new int[N];

		PriorityQueue<Makura> xsQueue = new PriorityQueue<>();

		for (int i = 0; i < N; i++) {
			int x = nextInt();
			y[i] = nextInt();
			xsQueue.add(new Makura(x, i));
		}

		PriorityQueue<Integer> ysQueue = new PriorityQueue<>();
		PriorityQueue<Integer> aQueue = new PriorityQueue<>();
		for (int i = 0; i < M; i++) {
			aQueue.add(nextInt());
		}

		int ans = 0;
		for (int h = 1; h <= MAX_H; h++) {

			while (!xsQueue.isEmpty() && xsQueue.peek().h == h) {
				ysQueue.add(y[xsQueue.poll().i]);
			}

			while (!aQueue.isEmpty() && aQueue.peek() == h) {
				aQueue.poll();
				while (!ysQueue.isEmpty() && ysQueue.peek() < h) {
					ysQueue.poll();
				}
				if (!ysQueue.isEmpty()) {
					ysQueue.poll();
					ans++;
				}
			}
			if (aQueue.isEmpty()) {
				break;
			}
		}
		System.out.println(ans);

	}

	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;
	}

}

class Makura implements Comparable<Makura> {
	int h, i;

	public Makura(int y, int i) {
		this.h = y;
		this.i = i;
	}

	@Override
	public int compareTo(Makura makura) {
		return this.h - makura.h;
	}

}