Overview

Based on participants’ desired departure times, when participants whose desired times differ by at most \(K\) can ride the same bus, find the minimum number of buses needed to transport everyone.

Analysis

In this problem, we are given a list of desired departure times \(T_1, T_2, \ldots, T_N\), and we need to minimize the number of groups (buses) by grouping participants whose times differ by at most \(K\).

A naive approach of trying all possible combinations for grouping would result in extremely large computational complexity and would not finish in time (TLE). Instead, we need a greedy strategy of “fitting as many as possible.”

Here is the key observation: When the desired departure times are sorted in ascending order, participants within a consecutive range can potentially ride the same bus.

In other words, after sorting, we scan from the beginning and use a greedy approach: “when a person who cannot fit on the current bus appears (i.e., the difference in desired times exceeds \(K\)), prepare a new bus.”

For example, consider the following input:

N = 5, K = 3
T = [1, 2, 8, 9, 10]

After sorting (which doesn’t change anything here), the first bus can accommodate people with times from 1 to 4 (2 is OK, but 8 is not). Therefore, times 1 and 2 go on one bus, and times 8, 9, and 10 go on another bus → 2 buses in total.

In this way, by sorting and scanning from the front, we can obtain the optimal solution.

Algorithm

1. Sort the list of desired departure times \(T\) in ascending order.
2. Set the first participant’s time as the reference time (start) for the first bus.
3. For each subsequent participant, if their desired time is within start + K, they ride the same bus.
4. When a person whose time exceeds start + K appears, prepare a new bus and set that person’s desired time as the new start.
5. Repeat this until all participants are processed, and count the number of buses used.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• Don’t forget to sort.
• Since the first participant is used as the starting reference, be careful with initial value setup.
• Within the loop, check “can this person ride the current bus?” and if not, increment the bus count.

## Source Code

```python
N, K = map(int, input().split())
T = list(map(int, input().split()))

T.sort()

count = 1
start = T[0]

for i in range(1, N):
    if T[i] - start > K:
        count += 1
        start = T[i]

print(count)

This editorial was generated by qwen3-coder-480b.