概要

各車が停められる区間 \([L_i, R_i]\) が与えられたとき、\(1\) 列に並ぶ \(N\) 個の駐車スペースへ重複なく全車を割り当てられるかを判定します。

考察

この問題は「区間に対して、各整数座標（駐車スペース）を高々1回ずつ使って、すべての区間から1点ずつ選べるか」という形になっています。

素朴な方法が難しい理由

• 各車ごとに「空いているスペースを探して埋める」を素直にやると、選び方次第で失敗したり（WA）、全探索に近くなって間に合いません（\(N, M \le 10^5\) なので \(O(NM)\) は不可）。
• 重要なのは「どの車を先に確定させるべきか」です。

重要な気づき（締切が早いものを優先）

ある時点で駐車スペース \(x\) を見ているとき、すでに \(L_i \le x\) を満たして「今なら停め始められる」車が複数あります。
この中で \(R_i\)（停められる最終位置）が最も小さい車 を優先して割り当てるのが安全です。

理由： - \(R_i\) が小さい車は「もうすぐ停められなくなる（締切が近い）」ので先に救わないと詰みやすい。 - 逆に \(R_i\) が大きい車は後ろのスペースにも逃げられるため、後回しにしても困りにくい。

さらに、もし「すでに開始可能な車の中に \(R_i < x\) のもの」があれば、それは 締切を過ぎてしまっており、どこにも割り当てられないので即 No です。

（例） - 車A: \([1,1]\), 車B: \([1,2]\) があり、スペース1を車Bに使うと車Aが行き場を失います。
したがって「締切が早い（\(R\) が小さい）車Aを先に」割り当てるべきです。

アルゴリズム

優先度付きキュー（min-heap）を使った貪欲法で判定します。

1. まず \(M > N\) なら物理的に無理なので No。
2. 車の区間 \([L_i, R_i]\) を \(L_i\) の昇順にソート。
3. 駐車スペース \(x = 1,2,\dots,N\) を左から順に見ていく（スイープ）：
   • \(L_i \le x\) を満たす車（つまりスペース\(x\)までに到達して「候補になった」車）をすべてヒープに追加する。
     ヒープには \(R_i\) を入れ、常に最小の \(R_i\) を取り出せるようにする。
   • ヒープの最小 \(R\) が \(x\) より小さい（\(R < x\)）なら、その車は締切超過なので No。
   • ヒープが空でなければ、ヒープから最小 \(R\) の車を1台取り出し、スペース \(x\) に割り当てる。
4. 割り当てた台数が \(M\) に到達したら Yes。
5. 最後まで見ても全車割り当てできなければ No。

この方法は「その時点で最も締切の近い車を救う」戦略で、将来の選択肢を最大化します。

計算量

• 時間計算量: ソートが \(O(M \log M)\)、各車のヒープ操作が高々1回 push + 1回 pop なので \(O(M \log M)\)、スイープは \(O(N)\)。合計で \(O((N+M)\log M)\)
• 空間計算量: 区間とヒープで最大 \(O(M)\)

実装のポイント

• intervals.sort() で \(L\) 昇順にし、スイープ中に「\(L \le x\) になった車」を順番にヒープへ追加します（添字 i を進める）。

• 締切超過判定 if hq and hq[0] < x: No は必須です。これがないと「すでに詰んでいる状況」を見逃します。

• 割り当てが完了したら（assigned == M）すぐ Yes を出して終了すると無駄がありません。

  ソースコード

import sys
import heapq

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    if M > N:
        print("No")
        return

    intervals = [tuple(map(int, input().split())) for _ in range(M)]
    intervals.sort()  # sort by L

    hq = []
    i = 0
    assigned = 0

    for x in range(1, N + 1):
        while i < M and intervals[i][0] <= x:
            heapq.heappush(hq, intervals[i][1])
            i += 1

        if hq and hq[0] < x:
            print("No")
            return

        if hq:
            heapq.heappop(hq)
            assigned += 1
            if assigned == M:
                print("Yes")
                return

    print("No")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。