概要

\(M\) 台の車それぞれに駐車可能な区間 \([L_i, R_i]\) が与えられるとき、すべての車を異なる駐車スペースに割り当てられるかを判定する問題です。これは区間スケジューリング問題の一種で、貪欲法で解けます。

考察

重要な気づき

この問題は「区間と点のマッチング」問題です。各車（区間 \([L_i, R_i]\)）に対して、その区間内の異なる駐車スペース（点）を1つずつ割り当てる必要があります。

素朴なアプローチの問題点

全ての割り当てパターンを試す方法では、最悪 \(O(M!)\) の計算量となり、\(M = 10^5\) では到底間に合いません。

解決の方針：貪欲法

駐車スペースを小さい番号から順に見ていき、「今この駐車スペースに割り当て可能な車のうち、締め切り（\(R_i\)）が最も早い車」を割り当てるのが最適です。

なぜこれが正しいのか？ - 締め切りが早い車ほど、後回しにすると割り当てられなくなるリスクが高い - 現時点で割り当て可能な車の中で、最も「余裕がない」車を優先することで、全体の成功確率を最大化できる

例えば、スペース3を処理中に、車A（区間[1,3]）と車B（区間[2,5]）が割り当て可能な場合： - 車Aの締め切りは3なので、スペース3が最後のチャンス - 車Bの締め切りは5なので、まだスペース4,5にも割り当てられる - よって、車Aをスペース3に割り当てるべき

アルゴリズム

1. 前処理: 全ての車を左端 \(L_i\) でソートする

2. 駐車スペースを1からNまで順に処理:

   • 現在のスペース番号に等しい \(L_i\) を持つ車を「割り当て候補」に追加
   • 候補の中で \(R_i\) が現在のスペースより小さい車があれば、その車は割り当て不可能 → No
   • 候補が存在すれば、\(R_i\) が最小の車をこのスペースに割り当てる（ヒープからpop）

3. 後処理: 全スペース処理後、まだ割り当てられていない車があれば No

4. 全ての車が割り当てられれば Yes

スペース:  1   2   3   4   5
車A [1,3]: ███████████
車B [2,5]:     █████████████████
車C [3,4]:         ███████

処理順:
- スペース1: 車Aが候補 → 車Aを割り当て
- スペース2: 車Bが候補 → 車Bを割り当て  
- スペース3: 車Cが候補 → 車Cを割り当て
→ 全車割り当て成功！

計算量

• 時間計算量: \(O(M \log M + N + M \log M) = O((N + M) \log M)\)

  • ソート: \(O(M \log M)\)
  • スペースの走査: \(O(N)\)
  • ヒープ操作: 各車は最大1回push、1回popなので \(O(M \log M)\)

• 空間計算量: \(O(M)\)

  • 車の情報とヒープの保持に必要

実装のポイント

1. 最小ヒープの活用: Pythonの heapq は最小ヒープなので、\(R_i\) をそのままpushすれば締め切りが早い車を効率的に取り出せる

2. 割り当て失敗の検出: ヒープから取り出す前に、先頭の \(R_i\) が現在のスペース番号より小さいかチェックする。小さければその車は既に締め切りを過ぎており、割り当て不可能

3. 全車の処理確認: ループ終了後、\(L_i > N\) の車や、候補に入ったが割り当てられなかった車が残っていないか確認が必要

   ソースコード

import heapq

def solve():
    N, M = map(int, input().split())
    cars = []
    for _ in range(M):
        L, R = map(int, input().split())
        cars.append((L, R))
    
    # Sort cars by their left endpoint (L_i)
    cars.sort()
    
    # Use a greedy approach: process parking spaces from 1 to N
    # For each space, assign it to the car with the smallest R_i among available cars
    
    # Events: for each car, we add it to available set when we reach its L_i
    car_idx = 0
    # Min-heap of R values for currently available cars
    available = []
    
    for space in range(1, N + 1):
        # Add all cars whose L_i equals current space
        while car_idx < M and cars[car_idx][0] == space:
            heapq.heappush(available, cars[car_idx][1])
            car_idx += 1
        
        # Remove cars whose R_i < current space (they can no longer be assigned)
        while available and available[0] < space:
            heapq.heappop(available)
        
        # If there are available cars, assign the one with smallest R_i to this space
        if available:
            heapq.heappop(available)
    
    # After processing all spaces, check if all cars have been assigned
    # We need to also add remaining cars and check
    while car_idx < M:
        heapq.heappush(available, cars[car_idx][1])
        car_idx += 1
    
    # Remove expired cars
    while available and available[0] < N + 1:
        # These cars couldn't be assigned
        if available[0] <= N:
            # This car's deadline has passed or is valid but wasn't assigned
            pass
        heapq.heappop(available)
    
    # Actually, let me reconsider the logic
    # After the loop, 'available' contains cars that were added but not assigned
    # If available is empty, all cars were assigned
    
    # Wait, the logic needs to be fixed. Let me redo this.
    
    # Reset and redo with correct logic
    cars.sort()
    car_idx = 0
    available = []
    assigned_count = 0
    
    for space in range(1, N + 1):
        # Add all cars whose L_i equals current space
        while car_idx < M and cars[car_idx][0] == space:
            heapq.heappush(available, cars[car_idx][1])
            car_idx += 1
        
        # Remove cars whose R_i < current space (they missed their chance)
        while available and available[0] < space:
            # This car cannot be assigned anymore - failure
            print("No")
            return
        
        # If there are available cars, assign the one with smallest R_i to this space
        if available:
            heapq.heappop(available)
            assigned_count += 1
    
    # After processing all spaces, check remaining cars
    # Add any remaining cars
    while car_idx < M:
        heapq.heappush(available, cars[car_idx][1])
        car_idx += 1
    
    # Check if any car in available has R_i <= N (meaning it should have been assigned but wasn't)
    while available:
        r = heapq.heappop(available)
        if r <= N:
            print("No")
            return
    
    # If we reach here, all cars were successfully assigned
    print("Yes")

solve()

この解説は claude4.5opus によって生成されました。