给定列车到发时刻表，能否以O(n)时间复杂度计算最小站台数？

Yes! Since the time range is fixed to 0-2399 (a constant 2400 discrete time points), we can leverage this constraint to build an O(n) solution, skipping the O(n logn) sorting step required by the standard approach.

Core Idea #

The key insight here is that the fixed 24-hour time window limits us to a constant number of possible time points. Any operation iterating over these points is effectively O(1) (constant time). We’ll use a difference array to track changes in occupied platforms, then compute the maximum number of overlapping trains—which directly equals the minimum number of platforms needed.

Step-by-Step Solution #

1. Initialize a Difference Array #

Create an array delta of size 4800 (twice the 24-hour range). This extra length lets us handle cross-day train schedules without messy circular logic, as it effectively represents two consecutive days of time points. Initialize all values to 0.

2. Populate the Difference Array #

For each train with arrival time a and departure time d:

• Same-day trains (a <= d):
  • Mark the arrival: delta[a] += 1 (platform count increases by 1 when the train arrives)
  • Mark the departure: delta[d + 1] -= 1 (platform count decreases by 1 right after the train departs)
• Cross-day trains (a > d):
  • This train occupies a platform from a to 2399 (current day) and from 0 to d (next day). Simplify this to a single cross-day interval:
    delta[a] += 1 (arrival on current day)
    delta[2400 + d + 1] -= 1 (departure right after next day's d time; 2400 corresponds to next day's 0)

3. Compute Prefix Sum and Find Maximum Platforms #

Iterate through the delta array to calculate the running count of occupied platforms, tracking the peak value:

current_platforms = 0
max_platforms = 0
for i in range(4800):
    current_platforms += delta[i]
    if current_platforms > max_platforms:
        max_platforms = current_platforms

The max_platforms value is exactly the minimum number of platforms required to avoid train waiting.

Verification with Examples #

Example 2 (Cross-Day Trains) #

Input: arr[] = {2200, 2300}, dep[] = {200, 300}

• First train (2200 → 200): delta[2200] +=1, delta[2601] -=1 (2400+200+1=2601)
• Second train (2300 →300): delta[2300] +=1, delta[2701] -=1 (2400+300+1=2701)
• Prefix sum peaks at 2 between 2300 (current day) and 200 (next day), matching the example output.

Example 3 (Three Cross-Day Trains) #

Input: arr[] = {2200,2300,0}, dep[] = {300,300,300}

• All three trains overlap between next day's 0 and 300.
• The prefix sum hits 3 in this interval, which matches the example output.

Why This Is O(n) Time #

• Populating the delta array takes O(n) time (one operation per train).
• Calculating the prefix sum takes O(4800) = O(1) time (constant, since 4800 is a fixed value).
• Total time complexity: O(n).

内容的提问来源于stack exchange，提问作者Rahul Chauhan