Overview

This is a problem where, given a list of bus arrival times, you need to find the minimum and maximum intervals between consecutive buses.

Analysis

The problem is very straightforward and can be solved by simply examining the given list of arrival times from the beginning and calculating the differences (intervals) between adjacent times. Since the arrival times are already given sorted in order of arrival, no additional sorting is necessary. A naive approach would be to calculate the differences of all adjacent pairs and find the minimum and maximum among them.

Algorithm

1. Read the number of buses \(N\) and the list of arrival times \(T_1, T_2, ..., T_N\).
2. Initialize the minimum interval to a very large value (\(\infty\)) and the maximum interval to 0.
3. Iterate index \(i\) from 1 to \(N-1\), and for each \(i\), calculate \(T_i - T_{i-1}\).
4. If the calculated interval is smaller than the current minimum interval, update it; if it is larger than the current maximum interval, update it.
5. Finally, output the resulting minimum and maximum intervals.

Complexity

• Time complexity: \(O(N)\)
  • Since we only scan the list of arrival times once, it can be processed in linear time.
• Space complexity: \(O(N)\)
  • Memory is used to store the list of arrival times.

Implementation Notes

• Since the list of arrival times is already sorted, we only need to sequentially calculate the differences between adjacent elements.

• The minimum value is initialized with a sufficiently large value (float('inf')), and the maximum value is initialized with 0.

• For reading input, sys.stdin.read().split() is used to read all data at once, achieving efficient processing.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    times = list(map(int, data[1:1+n]))
    
    min_interval = float('inf')
    max_interval = 0
    
    for i in range(1, n):
        interval = times[i] - times[i-1]
        if interval < min_interval:
            min_interval = interval
        if interval > max_interval:
            max_interval = interval
            
    print(f"{min_interval} {max_interval}")

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.