Overview

This problem asks for the minimum number of buses needed when grouping participants whose desired departure times differ by at most \(K\). This can be efficiently solved using a Greedy Algorithm.

Analysis

Key Insight

The condition that any two participants on the same bus must have a time difference of at most \(K\) can be rephrased as: “Among all participants on that bus, the difference between the maximum and minimum times must be at most \(K\).”

For example, when \(K = 5\): - 3 people with times \([2, 4, 7]\) → max 7, min 2, difference is 5 → OK (can ride the same bus) - 3 people with times \([2, 4, 8]\) → max 8, min 2, difference is 6 → NG (cannot ride the same bus)

Why Greedy Works

After sorting participants by their desired departure times, the following greedy approach gives the optimal solution:

1. Assign people to buses in order, starting from the person with the earliest time
2. Put as many people as possible on each bus while satisfying the condition

Why is this optimal? After sorting, once we decide the first person (minimum time) for a bus, it’s best to include everyone whose “time is at most minimum time \(+ K\)” on that bus. Cutting off earlier might require extra buses later.

Concrete Example

For \(N = 5\), \(K = 3\), \(T = [1, 5, 2, 9, 6]\):

After sorting: \([1, 2, 5, 6, 9]\)

• Bus 1: Start from time 1 → 1, 2 (time 5 has \(5-1=4 > K\), so NG)
• Bus 2: Start from time 5 → 5, 6 (time 9 has \(9-5=4 > K\), so NG)
• Bus 3: Start from time 9 → 9

Answer: 3 buses

Algorithm

1. Sort the desired departure times \(T\) in ascending order
2. Scan from the beginning, and each time a new bus is created:
   • Record the reference time (minimum time) for that bus
   • Keep adding participants to the same bus as long as “current participant’s time - reference time \(\leq K\)”
   • When the condition is no longer satisfied, prepare the next bus
3. Output the number of buses used

buses = 0
i = 0
while i < N:
    buses += 1
    start_time = T[i]  # Reference time for this bus
    while i < N and T[i] - start_time <= K:
        i += 1
print(buses)

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(N)\) for scanning (each participant is examined once)
• Space complexity: \(O(N)\)
  • Required for storing array \(T\)

Implementation Notes

• Sorting is essential: Without sorting, it becomes difficult to determine which participants should be assigned to which bus
• Managing reference time: Remember the “time of the first person on each bus” and use the difference from it for comparison
• When \(K = 0\): Only people with the same time can ride the same bus. This code handles this correctly
• Overflow caution: \(T_i\) and \(K\) can be up to \(10^9\), but since we only take differences, there’s no issue in Python

Source Code

def solve():
    N, K = map(int, input().split())
    T = list(map(int, input().split()))
    
    # Sort by desired departure time
    T.sort()
    
    buses = 0
    i = 0
    
    while i < N:
        # Start a new bus
        buses += 1
        # Reference time (minimum time) for this bus
        start_time = T[i]
        # Put all participants who can ride this bus on board
        # Condition for riding the same bus: all time differences <= K = max time - min time <= K
        while i < N and T[i] - start_time <= K:
            i += 1
    
    print(buses)

solve()

---

This editorial was generated by claude4.5opus.