Overview

Bus arrival times are given in ascending order. The task is to compute the intervals between all consecutive buses and find the minimum and maximum of those intervals.

Analysis

What we want to find in this problem is the minimum and maximum of the “intervals between consecutive buses.”

Since the arrival times are sorted in ascending order as \(T_1 < T_2 < \cdots < T_N\), the intervals between consecutive buses are the following \(N-1\) values:

\[T_2 - T_1, \quad T_3 - T_2, \quad \ldots, \quad T_N - T_{N-1}\]

For example, if \(N = 4\) and the arrival times are 100 300 450 1200: - \(300 - 100 = 200\) (seconds) - \(450 - 300 = 150\) (seconds) - \(1200 - 450 = 750\) (seconds)

The minimum is \(150\) and the maximum is \(750\).

For this problem, it is sufficient to simply compute all differences and find the minimum and maximum. Since \(N\) is at most \(2 \times 10^5\), an \(O(N)\) approach that computes the \(N-1\) differences and finds the minimum and maximum among them runs well within the time limit.

Algorithm

1. Read the arrival times \(T_1, T_2, \ldots, T_N\) of the \(N\) buses.
2. Compute all differences (intervals) between consecutive arrival times and store them in a list diffs.
   • diffs[i] = T[i+1] - T[i] (\(i = 0, 1, \ldots, N-2\))
3. Output the minimum and maximum of diffs.

Complexity

• Time complexity: \(O(N)\)
  • Creating the difference list takes \(O(N)\), and computing the minimum and maximum each take \(O(N)\), for a total of \(O(N)\).
• Space complexity: \(O(N)\)
  • Storing the list of arrival times and the difference list requires \(O(N)\).

Implementation Notes

• Using Python’s list comprehension [T[i+1] - T[i] for i in range(N-1)] allows you to create the difference list concisely.

• Using min() and max() lets you retrieve the minimum and maximum from a list in one call each.

• Since the arrival times are strictly monotonically increasing (all distinct and in ascending order), the differences are always positive. No special case handling is needed.

  Source Code

N = int(input())
T = list(map(int, input().split()))
diffs = [T[i+1] - T[i] for i in range(N-1)]
print(min(diffs), max(diffs))

---

This editorial was generated by claude4.6opus-thinking.