Overview

When \(N\) students board a bus at times \(T_i\) respectively, find the time that is \(K\) minutes after the last student boards.

Analysis

The key point in this problem is identifying “the time when the last student boards the bus.”

• The times when students board the bus are scattered as \(T_1, T_2, \ldots, T_N\)
• “The last student” refers to the student who boards the bus at the latest time
• In other words, we need to find the maximum value among \(T_1, T_2, \ldots, T_N\)

Let’s think through a concrete example

For example, with \(N = 3\), \(K = 5\), and boarding times \(T = [10, 25, 15]\):

• Student 1 boards at time \(10\)
• Student 2 boards at time \(25\) (the latest)
• Student 3 boards at time \(15\)

Since the last student (Student 2) boards at time \(25\), the departure signal will be at time \(25 + 5 = 30\).

Is a naive approach sufficient?

This problem simply requires “finding the maximum value in the array and adding \(K\),” so a naive approach solves it quickly enough. Finding the maximum value in an array is possible in \(O(N)\), which is completely fine given the constraint \(N \leq 10^5\).

Algorithm

1. Read \(N\), \(K\), and the list of boarding times \(T\) from input
2. Find the maximum value in list \(T\) (this is the time when the last student boards)
3. Output the maximum value plus \(K\)

In Python, you can easily find the maximum value in a list using the max() function.

Complexity

• Time complexity: \(O(N)\)
  • We need to check each element once to find the maximum value in the list
• Space complexity: \(O(N)\)
  • Space is needed to store the input list \(T\)

Implementation Notes

• Using Python’s built-in function max(), you can get the maximum value in a single line

• Since the maximum value of \(T_i\) is \(10^9\) and the maximum value of \(K\) is \(10^4\), the answer can be at most about \(10^9\), but in Python there’s no need to worry about integer overflow

• You could also sort and find the maximum value (\(O(N \log N)\)), but using max() is more efficient (\(O(N)\))

  Source Code

N, K = map(int, input().split())
T = list(map(int, input().split()))
print(max(T) + K)

---

This editorial was generated by claude4.5opus.