Overview

Given the arrival times of buses, find the minimum and maximum intervals between consecutive pairs of buses.

Analysis

In this problem, since the arrival times are given in strictly increasing order, the difference between adjacent times (\(T_{i+1} - T_i\)) directly gives the arrival interval.

A naive approach would be to compute the intervals for all pairs and find the minimum and maximum, but this involves many unnecessary computations and is not efficient. Moreover, since the input size can be up to \(N = 2 \times 10^5\), using a double loop could result in exceeding the time limit (TLE).

However, by leveraging the property that the arrival times are already sorted, it suffices to only look at differences between adjacent elements, and we can examine all intervals in a single loop.

Therefore, the problem can be solved in \(O(N)\).

Algorithm

1. Read each arrival time \(T_i\) into a list.
2. Compute the differences \(T_{i+1} - T_i\) between adjacent times sequentially.
3. Update the minimum and maximum values each time.
4. Finally, output the minimum and maximum values.

For example, when the input is T = [100, 200, 250, 400]: - The differences are \([100, 50, 150]\), so the minimum is \(50\) and the maximum is \(150\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for the input array)

Implementation Notes

• Be careful with initial values: initialize the minimum with a sufficiently large value (float('inf')) and the maximum with a sufficiently small value (-float('inf')).
• The loop range is from \(i = 0\) to \(N - 2\) (i.e., there are \(N - 1\) differences).

## Source Code

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

min_diff = float('inf')
max_diff = -float('inf')

for i in range(N - 1):
    diff = T[i + 1] - T[i]
    min_diff = min(min_diff, diff)
    max_diff = max(max_diff, diff)

print(min_diff, max_diff)

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