概要

\(M\) 台の車を、それぞれが指定された範囲 \([L_i, R_i]\) 内の重複しない駐車スペースに割り当てられるかを判定する問題です。この問題は、締め切りが早いものから優先的に処理する「区間スケジューリング」の考え方を応用した貪欲法で効率的に解くことができます。

考察

重要な気づき

複数の車が同じ駐車スペース \(x\) に駐車可能なとき、どの車を優先的に割り当てるべきでしょうか？

結論から言うと、「駐車可能な右端 \(R_i\)（締め切り）が最も近い車」を優先するのが最適です。 なぜなら、右端 \(R_j\) が遠い車は、後のスペース（ \(x+1\) 以降）に駐車できる可能性が高いのに対し、右端 \(R_i\) が近い車は、今ここで駐車しておかないと、すぐに駐車可能な範囲を通り過ぎてしまう（＝失敗する）リスクが高いからです。

なぜ素朴な方法ではいけないのか

「各スペース \(1 \dots N\) について、停められる車を全探索する」といった素朴な方法では、車の数 \(M\) とスペースの数 \(N\) がともに \(10^5\) であるため、計算時間が \(O(N \times M)\) になり、実行時間制限（TLE）に間に合いません。

解決策

1. 車を左端 \(L_i\) の昇順にソートし、駐車スペースを \(1\) 番から順に見ていきます。
2. 現在のスペース \(curr\_pos\) で駐車可能な車（\(L_i \le curr\_pos\) となる車）をすべて候補に入れます。
3. 候補の中で最も \(R_i\) が小さい車を \(curr\_pos\) に割り当てます。
4. 効率的に「最小の \(R_i\)」を取り出すために、優先度付きキュー（ヒープ）を利用します。

アルゴリズム

1. 車のリストを \(L_i\) の昇順にソートします。
2. 優先度付きキュー pq を用意します（ここには駐車可能な車の \(R_i\) を格納します）。
3. 現在の駐車スペースの番号を curr_pos = 1 とします。
4. 以下の操作を、すべての車を処理し終えるまで繰り返します：
   • pq が空の場合、次に駐車可能な車が現れる位置まで curr_pos をジャンプさせます（curr_pos = max(curr_pos, cars[car_idx].L)）。
   • L_i <= curr_pos を満たすすべての車の \(R_i\) を pq に追加します。
   • pq から最小の \(R_i\) を取り出します。
     • もし R_i < curr_pos であれば、その車はどのスペースにも駐車できなかったことになるため、 No を出力して終了します。
   • 車を 1 台割り当てたので、curr_pos を 1 進めます。
5. すべての車を無事に割り当てられたら Yes を出力します。

計算量

• 時間計算量: \(O(M \log M)\)
  • 車のソートに \(O(M \log M)\) かかります。
  • 各車は優先度付きキューに 1 回追加され、1 回取り出されるため、キューの操作合計は \(O(M \log M)\) です。
  • 駐車スペースの走査は、車の存在する範囲のみをジャンプしながら行うため、全体で \(O(M)\) 程度のステップ数になります。
• 空間計算量: \(O(M)\)
  • 車を格納するリストと優先度付きキューに最大 \(M\) 個の要素が格納されます。

実装のポイント

• 鳩の巣原理による早期判定: 車の数 \(M\) がスペースの数 \(N\) より多い場合、絶対に割り当て不可能なので、最初に No と判定できます。

• 高速な入出力: \(N, M\) が大きいため、Python の場合は sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。

• 空きスペースのスキップ: 車が全く駐車できない範囲が長い場合、curr_pos を 1 ずつ増やすのではなく、次に利用可能な車の \(L_i\) まで飛ばすことで効率化しています。

  ソースコード

import sys
import heapq

def solve():
    # Read all input at once and split into tokens for efficient processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of parking spaces, M is the number of cars
    N = int(input_data[0])
    M = int(input_data[1])
    
    # Basic pigeonhole principle: if there are more cars than spaces, it's impossible
    if M > N:
        print("No")
        return
    
    # Parse the parking range [L_i, R_i] for each car
    cars = []
    for i in range(M):
        l = int(input_data[2 + 2 * i])
        r = int(input_data[3 + 2 * i])
        cars.append((l, r))
    
    # Sort cars by their earliest possible parking space (L_i)
    cars.sort()
    
    # Use a priority queue (min-heap) to store the deadlines (R_i) of cars 
    # that are eligible to be parked at or after the current position.
    pq = []
    car_idx = 0
    curr_pos = 1
    parked_count = 0
    
    # Greedy strategy: At each available parking space, assign the car 
    # that has the earliest deadline (smallest R_i).
    while car_idx < M or pq:
        # If no cars are currently eligible for the current space, 
        # jump to the next car's earliest possible starting space.
        if not pq:
            if car_idx < M:
                curr_pos = max(curr_pos, cars[car_idx][0])
        
        # Add all cars that can start being parked at or before the current space
        while car_idx < M and cars[car_idx][0] <= curr_pos:
            heapq.heappush(pq, cars[car_idx][1])
            car_idx += 1
        
        # If there are cars that can be parked in the current space
        if pq:
            # If the current space index exceeds the total number of spaces
            if curr_pos > N:
                print("No")
                return
            
            # Pick the car with the earliest deadline (smallest R_i)
            earliest_deadline = heapq.heappop(pq)
            
            # If the car's latest possible parking space is before the current space, 
            # it means this car cannot be parked anywhere.
            if earliest_deadline < curr_pos:
                print("No")
                return
            
            # Successfully assigned a space to one car
            parked_count += 1
            curr_pos += 1
            
    # Check if every car was assigned a parking space
    if parked_count == M:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。