概要

バスの到着時刻のリストから、連続する2本のバス間の到着間隔の最小値と最大値を求める問題です。

考察

問題は非常にシンプルで、与えられた到着時刻のリストを先頭から順に調べ、隣り合う時刻の差（間隔）を計算していくだけで解けます。到着時刻はすでに到着順にソートされて与えられるため、追加のソートは必要ありません。素朴なアプローチとして、すべての隣接ペアの差を計算し、その中から最小値と最大値を探す方法が考えられます。

アルゴリズム

1. 入力されたバスの本数 \(N\) と到着時刻のリスト \(T_1, T_2, ..., T_N\) を受け取ります。
2. 最小間隔を非常に大きな値（\(\infty\)）、最大間隔を0で初期化します。
3. インデックス \(i\) を1から \(N-1\) まで動かし、各 \(i\) について \(T_i - T_{i-1}\) を計算します。
4. 計算した間隔が現在の最小間隔より小さければ更新し、現在の最大間隔より大きければ更新します。
5. 最後に求めた最小間隔と最大間隔を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 到着時刻のリストを1回だけ走査するため、線形時間で処理できます。
• 空間計算量: \(O(N)\)
  • 到着時刻のリストを保持するためのメモリを使用します。

実装のポイント

• 到着時刻のリストはすでにソートされているため、隣接する要素の差を順に計算するだけで良いです。

• 最小値の初期化には十分に大きな値（float('inf')）を使用し、最大値の初期化には0を使用しています。

• 入力の読み込みでは、sys.stdin.read().split() を使用して一度にすべてのデータを読み込むことで、効率的な処理を実現しています。

  ソースコード

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()

---

この解説は deepseekv3 によって生成されました。