Railway Station | TCS CodeVita 9 Solution (Zone 1) 2020

Railway Station from TCS CodeVita Season 9 (Zone 1) is the well-known "minimum platforms" problem. Trains arrive, wait for a while and leave, and you need to find the least number of platforms so that no train ever waits for a free one. Underneath, it asks for the maximum number of time intervals that overlap at any single moment.

The same idea solves meeting-room booking, CPU scheduling and "how many servers do we need at peak" questions, so it is worth learning properly. The neat part is that you can answer it without tracking which train is on which platform.

Problem

You are given N trains. For each one you know its arrival time a and how long it stays at the station, b. A train occupies a platform from a until it leaves at a + b. Find the minimum number of platforms needed so every train gets one.

One rule needs care: if one train leaves at time x and another arrives at exactly x, the arriving train cannot use the platform that is being freed. Touching at the same instant counts as an overlap.

Input format: the first line has N. Then come N pairs of integers, each pair being the arrival time and the stoppage time of one train.

Output format: one integer, the minimum number of platforms.

Constraints: 1 <= N <= 10^5, 0 <= a <= 86400, 0 < b <= 86400, and the answer is at least 1. Time limit 1 second.

The sample in the original statement puts everything on a single line. Reading with cin handles that fine, since it skips any whitespace, including newlines.

Input
3 10 2 5 10 13 5

Output
2

So there are 3 trains: (arrive 10, stay 2), (arrive 5, stay 10) and (arrive 13, stay 5). The train arriving at 5 stays until 15, so the one arriving at 10 needs a second platform. That train leaves at 12, so the train arriving at 13 can reuse platform 2. The answer is 2.

Approach

Picture a timeline. Every arrival adds one train to the station, and every departure removes one. The number of platforms you need is the highest number of trains present at the same time. You do not need to know which train is which, only the order of events.

1. Build two arrays: all arrival times, and all departure times (a + b).
2. Sort both arrays separately.
3. Walk through them with two pointers, like the merge step of merge sort. At each step take the earlier event.
4. If the next arrival is at or before the next departure, a train comes in: increase the count and update the maximum. Otherwise a train leaves: decrease the count.

The "at or before" (<=) is how we apply the rule about equal times. When an arrival and a departure happen at the same moment, we process the arrival first, so both trains are counted together.

Dry run. Arrivals sorted: 5, 10, 13. Departures sorted: 12, 15, 18.

• 5 <= 12: arrival, count 1, max 1
• 10 <= 12: arrival, count 2, max 2
• 13 > 12: departure, count 1
• 13 <= 15: arrival, count 2, max stays 2

All arrivals are processed, so the answer is 2. We can stop once arrivals run out, because departures only lower the count.

Solution in C++

The older solution here used the same two-pointer method and was correct. I rewrote it with vector instead of variable-length arrays (which are not standard C++ and can overflow the stack for large N), and with clearer names.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> arr(n), dep(n);
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;          // arrival time and stoppage time
        arr[i] = a;
        dep[i] = a + b;         // departure time
    }

    sort(arr.begin(), arr.end());
    sort(dep.begin(), dep.end());

    int i = 0, j = 0;           // i walks arrivals, j walks departures
    int onPlatform = 0, best = 0;
    while (i < n) {
        // "<=" because a train arriving exactly when another leaves
        // still needs a different platform
        if (arr[i] <= dep[j]) {
            onPlatform++;       // a train comes in
            best = max(best, onPlatform);
            i++;
        } else {
            onPlatform--;       // a train has already left
            j++;
        }
    }
    cout << best << "\n";
    return 0;
}

Edge cases I ran: one train (1 / 0 86400) gives 1. Two trains where the second arrives exactly when the first leaves (0 5 and 5 3) gives 2, as the rule demands. If the second arrives one second later (6 3), the answer drops to 1. Three trains arriving together gives 3. I also compared the output with a brute-force checker that counts trains present at every second, on 500 random inputs, with no differences.

Output

2

Complexity

Time: O(N log N) for the two sorts. The two-pointer walk is O(N).

Space: O(N) for the arrival and departure arrays.

Common mistakes

• Using < instead of <=. Then a train arriving exactly at another's departure would share the platform, which the statement forbids. You would under-count.
• Sorting trains as pairs and comparing only neighbours. A long-staying early train can overlap many later ones. Checking just consecutive trains misses that.
• Reading input as "one train per line". The sample has everything on one line. Token-based reading (cin >> or scanf) is safer than getline.
• Treating b as the departure time. The second number is how long the train stays, so the departure is a + b.

Related: Parenting Partnering Returns from Google Code Jam is another interval-overlap problem, and Count Pairs is from the same CodeVita round.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More TCS CodeVita solutions All coding problems MCQ practice