概要

来客を番号順に 1 人ずつ処理していくとき、「今の時点で窓口の対応がいつ終わるか」だけを持って順番に更新していけば、最後の来客の終了時刻を求められます。

考察

この問題では、来客 \(i\) の対応開始時刻 \(S_i\) は

• 前の来客の対応が終わっている
• その来客自身が到着している

の両方を満たす最も早い時刻です。
つまり、開始時刻は

\(S_i = \max(\text{前の来客の終了時刻},\ A_i)\)

となります。

そして終了時刻は

\(S_i + B_i\)

です。

---

ここで重要なのは、必要なのは「直前までの対応終了時刻」だけということです。

たとえば、現在の窓口の終了予定時刻を current_end とすると、次の来客 \((A, B)\) に対しては次の 2 通りです。

• current_end < A
  まだ来客が来ていないので、窓口は一度空く
  \(\rightarrow\) 到着を待って、時刻 \(A\) から開始し、終了は \(A + B\)

• current_end >= A
  来客はもう到着済みなので、前の対応が終わり次第すぐ開始
  \(\rightarrow\) 終了は current_end + B

つまり更新式は

• current_end = A + B （窓口が空いて待つ場合）
• current_end += B （待っている来客をすぐ処理する場合）

となります。

---

具体例

例えば次のような入力を考えます。

• 来客 1: \((A_1, B_1) = (2, 3)\)
• 来客 2: \((A_2, B_2) = (4, 5)\)
• 来客 3: \((A_3, B_3) = (10, 2)\)

順に見ていくと：

1. 最初は current_end = 0
2. 来客 1 は時刻 2 に到着
   窓口は空いているので、時刻 2 から開始して時刻 \(2+3=5\) に終了
   current_end = 5
3. 来客 2 は時刻 4 に到着
   すでに来客 2 は到着済みで、窓口は時刻 5 に空く
   時刻 5 から開始して時刻 \(5+5=10\) に終了
   current_end = 10
4. 来客 3 は時刻 10 に到着
   ちょうど窓口が空く時刻なので、すぐ開始して時刻 \(10+2=12\) に終了
   current_end = 12

答えは \(12\) です。

---

素朴な方法がよくない理由

時刻を 1 ずつ進めて「今誰を処理しているか」をシミュレーションすると、時刻は最大で \(10^9\) 以上になる可能性があり、間に合いません。

しかしこの問題では、各来客について
「前の終了時刻」と「自分の到着時刻」の大きい方から始める
だけでよいので、1 人ずつ見る \(O(N)\) の処理で十分です。

アルゴリズム

current_end を「ここまでの来客の対応がすべて終わる時刻」とします。

1. current_end = 0 で初期化する
2. 各来客 \((A_i, B_i)\) について順に以下を行う
   • もし current_end < A_i なら、窓口は来客の到着まで空いている
     \(\rightarrow\) current_end = A_i + B_i
   • そうでなければ、来客はすでに到着済み
     \(\rightarrow\) current_end += B_i
3. 最後に current_end を出力する

この current_end が、最後の来客の対応終了時刻そのものです。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 開始時刻そのものを変数として持たなくても、終了時刻だけを更新すれば十分です。

• \(A_i, B_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、答えは大きくなります。Python の整数なら問題ありません。

• 入力が多いため、input = sys.stdin.readline を使うと高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    current_end = 0

    for _ in range(N):
        A, B = map(int, input().split())
        if current_end < A:
            current_end = A + B
        else:
            current_end += B

    print(current_end)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。