Overview

This problem asks us to determine whether \(M\) cars can each be assigned to a distinct parking space within their specified range \([L_i, R_i]\). It can be efficiently solved using a greedy algorithm that applies the concept of “interval scheduling,” where items with the earliest deadlines are processed first.

Analysis

Key Insight

When multiple cars can park at the same parking space \(x\), which car should be prioritized for assignment?

The conclusion is that it is optimal to prioritize the car with the smallest right endpoint \(R_i\) (i.e., the earliest deadline). This is because a car with a distant right endpoint \(R_j\) has a higher chance of being able to park at a later space (\(x+1\) or beyond), whereas a car with a close right endpoint \(R_i\) carries a high risk of passing beyond its parkable range (= failing) if it is not parked here and now.

Why a Naive Approach Doesn’t Work

A naive approach such as “for each space \(1 \dots N\), exhaustively search for a car that can park there” would result in a time complexity of \(O(N \times M)\), since both the number of cars \(M\) and the number of spaces \(N\) can be up to \(10^5\), which would exceed the time limit (TLE).

Solution

1. Sort the cars in ascending order of their left endpoint \(L_i\), and examine parking spaces starting from space \(1\).
2. Add all cars that can park at the current space \(curr\_pos\) (i.e., cars with \(L_i \le curr\_pos\)) to the candidate pool.
3. Assign the car with the smallest \(R_i\) among the candidates to \(curr\_pos\).
4. Use a priority queue (heap) to efficiently extract the minimum \(R_i\).

Algorithm

1. Sort the list of cars in ascending order of \(L_i\).
2. Prepare a priority queue pq (which stores the \(R_i\) values of parkable cars).
3. Set the current parking space number to curr_pos = 1.
4. Repeat the following operations until all cars have been processed:
   • If pq is empty, jump curr_pos to the position where the next parkable car appears (curr_pos = max(curr_pos, cars[car_idx].L)).
   • Add \(R_i\) to pq for all cars satisfying \(L_i \le curr\_pos\).
   • Extract the minimum \(R_i\) from pq.
     • If \(R_i < curr\_pos\), this means the car could not be parked at any space, so output No and terminate.
   • Since one car has been assigned, increment curr_pos by 1.
5. If all cars have been successfully assigned, output Yes.

Complexity

• Time Complexity: \(O(M \log M)\)
  • Sorting the cars takes \(O(M \log M)\).
  • Each car is added to and removed from the priority queue exactly once, so the total queue operations are \(O(M \log M)\).
  • The scan over parking spaces jumps only through ranges where cars exist, resulting in about \(O(M)\) total steps.
• Space Complexity: \(O(M)\)
  • The list storing cars and the priority queue hold at most \(M\) elements.

Implementation Notes

• Early termination via the pigeonhole principle: If the number of cars \(M\) exceeds the number of spaces \(N\), assignment is impossible, so we can immediately output No.

• Fast I/O: Since \(N\) and \(M\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() or similar methods.

• Skipping empty spaces: When there is a long range where no car can park, instead of incrementing curr_pos one by one, we improve efficiency by jumping directly to the \(L_i\) of the next available car.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.