Overview

This problem asks for the minimum number of buses needed when dividing \(N\) participants into groups such that the difference in desired departure times between any two members riding the same bus is at most \(K\).

Key Insight

The crux of this problem is how to efficiently handle the condition that “the difference between any two people on the same bus is at most \(K\)”.

This condition is equivalent to the following: if we let \(T_{min}\) be the earliest departure time and \(T_{max}\) be the latest departure time among all people on that bus, then \(T_{max} - T_{min} \le K\).

To find the minimum number of buses, we think through the following steps: 1. Sort: Since it’s difficult to handle departure times when they’re in random order, we first sort \(T_i\) in ascending order. 2. Decide from one end (greedy approach): The person with the earliest departure time must ride some bus. It is most efficient to assign that person as the one with the earliest departure time (\(T_{min}\)) on their bus. This is because we can fit everyone with a departure time up to \(T_{min} + K\) onto that same bus.

In this way, we can obtain the optimal solution by repeatedly applying the following greedy approach: among people who haven’t been assigned a bus yet, take the one with the earliest time as the reference, and group all people within \(K\) of that time onto one bus.

Algorithm

1. Sort the participants’ desired departure times \(T\) in ascending order.
2. Count the number of buses using the following procedure:
   • Among participants who haven’t been assigned a bus yet, let \(T_{start}\) be the earliest departure time.
   • Prepare a new bus and assign all participants with departure times at most \(T_{start} + K\) to that bus.
   • Repeat this until everyone has been assigned a bus.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the departure times takes \(O(N \log N)\).
  • The subsequent bus assignment (scanning the list) is \(O(N)\).
  • Overall, the sorting step dominates.
• Space complexity: \(O(N)\)
  • Memory is needed to store the departure times of \(N\) participants.

Implementation Notes

• Importance of sorting: Performing t.sort() at the beginning is essential for applying the greedy approach.

• Efficient traversal: By using a while loop or for loop and skipping participants that have already been processed, unnecessary computation can be avoided.

• Handling large values: Since \(N\) and \(T_i\) can be large, in Python it is safer to use fast I/O methods such as sys.stdin.read.

  Source Code

import sys

def solve():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    t = list(map(int, input_data[2:]))
    
    # 出発時刻を昇順にソート
    t.sort()
    
    if n == 0:
        print(0)
        return

    # 最小のバス台数を求める貪欲法
    count = 0
    i = 0
    while i < n:
        count += 1
        # 現在のバスに乗せる最初の人の出発時刻
        start_time = t[i]
        # その人との出発時刻の差がK以内の人を同じバスに含める
        # ソート済みなので、t[i]がそのバスの中での最小値となる
        # 条件「同じバスに乗るどの2人の差もK以下」は
        # 「最大値 - 最小値 <= K」と同値
        while i < n and t[i] - start_time <= k:
            i += 1
            
    print(count)

if __name__ == "__main__":
    solve()

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