CODE FESTIVAL 2014 Easy D - 枕決め

知らないと解けないなと思ったのでメモ。参考
CODE FESTIVAL 2014 あさプロMiddle : B - 枕決め - kmjp's blog

N人の人とM個の枕がある。
N人はそれぞれ高さがX[i]以上Y[i]以下の枕が好みであり、そのような枕を１個使いたい。
M個の枕の高さA[0] ~ A[m]が与えられるとき、最大何人が好みの枕を使えるか。

解き方
まず (X[i], Y[i]) を List[x[i]].append(Y[i]) として前処理する。
次に高さの下限1から上限100000まで以下の処理を行う。今見ている高さをhとすると：

最初に作った配列を参照し、X[i]==hであるような人がいたら、(List[h] != [ ] であるなら）
List[h] の要素を heap に入れる。
heap から A[i]==h な枕の数だけ、heap からY[i]の低い順に枕を割り当てる。
heap には「h以上の枕が好みの人が、Y[i]の低い順に入っている」という状態にしておくことで、以後登場する枕をY[i]の低い順に割り当てることができる。
X ≦ Y であり、h(X) の小さい順に調べているので、heappop したときに、Y[i] ≧ h ならば
その i さんは X[i] ≦ h ≦ Y[i] を満たす枕が存在し、割り当てることが最適といえる。
逆に、Y[i] ＜ h ならば好みの枕は割り当てないことが最適といえる。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heapify,heappop,heappush

n,m = map(int,readline().split())
xy = [list(map(int,readline().split())) for i in range(n)]

a = [int(readline()) for i in range(m)]
A = [0]*100001; Y = [[] for i in range(100001)]
for i in a:
  A[i] += 1
for x,y in xy:
  Y[x].append(y)

que = []; heapify(que)
ans = 0
for h in range(1,100001):
  for y in Y[h]:
    heappush(que,y)
  while A[h]:
    if que == []:
      break
    yy = heappop(que)
    if yy >= h:
      ans += 1
      A[h] -= 1
      
print(ans)