Overview

Given \(N\) people each with a desired departure time \(T_i\), we need to divide them into groups such that “the time difference between any two people in the same bus is at most \(K\)”, and find the minimum number of buses required.

Analysis

Key Insight

The condition for riding the same bus can be rephrased as “maximum time − minimum time in the bus \(\le K\).”
This is because if the minimum in a group is \(a\) and the maximum is \(b\), then the maximum difference between any two people is \(b - a\), and if this is at most \(K\), all pairs satisfy the condition.

Therefore, when the participants’ times are sorted in ascending order, the people on one bus can optimally be taken as a contiguous interval (consecutive sequence). There is no need to skip anyone in between (a skipped person has a time within that range, so if the condition is satisfied, they can be included).

Why a Naive Approach is Difficult

• Exhaustively searching “who rides with whom” leads to a combinatorial explosion.
• An approach that searches for the “maximum set that can fit in the same bus” for each person is \(O(N^2)\) in the worst case, which is too slow for \(N \le 2 \times 10^5\).

How to Solve It

Sort the times, and starting from the earliest unassigned person, greedily pack subsequent people into the same bus as long as the condition \(T[j] - T[i] \le K\) holds.
This way, each bus carries as many people as possible (all within \(K\) of the starting time), minimizing the remaining people and thus minimizing the number of buses.

Concrete example: - \(T = [1, 2, 3, 7, 8],\ K = 2\) (already sorted) - Starting from person \(1\), we can include up to \(1 + 2 = 3\), so \(\{1, 2, 3\}\) fills 1 bus. - Next, starting from person \(7\), we can include up to \(7 + 2 = 9\), so \(\{7, 8\}\) fills 1 bus.
→ Total: 2 buses

Algorithm

1. Sort the array \(T\) in ascending order.
2. Place a pointer \(i\) at the beginning, and repeat while there are unassigned people:
   • Add a new bus.
   • Set the minimum time of that bus as start = T[i].
   • Advance \(i\) while T[i] - start <= K holds, assigning those people to the same bus (i.e., increment \(i\)).
3. Output the number of buses added.

This method is a greedy algorithm that “packs each bus to its maximum possible range.” Since the problem becomes an interval partitioning problem on the sorted sequence, this approach is optimal.

Complexity

• Time complexity: \(O(N \log N)\) for sorting, \(O(N)\) for the scan, so \(O(N \log N)\) in total.
• Space complexity: \(O(N)\) for the sorted array, etc.

Implementation Notes

• The condition is about “any two people in the same bus,” but after sorting, it suffices to only check “the difference from the minimum (the first element),” reducing it to the check T[i] - start <= K.

• Since \(N\) can be large, using sys.stdin.buffer.read() for input is faster.

• The scan may look like a nested loop, but since the pointer \(i\) advances from \(0\) to \(N\) only once in total, the scan portion is effectively \(O(N)\).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    T = data[2:2+N]
    T.sort()

    buses = 0
    i = 0
    while i < N:
        buses += 1
        start = T[i]
        i += 1
        while i < N and T[i] - start <= K:
            i += 1

    print(buses)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.