Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Greedy

Minimum Platforms

Medium · Greedy · Asked at Amazon, Microsoft, Flipkart, Walmart

Given arrival and departure times of trains (in minutes from midnight), find the minimum number of platforms so no train waits. A train that arrives at the same minute another departs needs a separate platform.

Input

Line 1: n. Line 2: n arrival times. Line 3: n departure times (departure ≥ arrival).

Output

The minimum number of platforms.

Constraints

Sort arrivals and departures separately and sweep with two pointers.

Example 1

Input

6
900 940 950 1100 1500 1800
910 1200 1120 1130 1900 2000

Output

3

Example 2

Input

3
900 1100 1235
1000 1200 1240

Output

1

Hints

  1. The answer is the largest number of trains at the station at the same moment.
  2. Sort arrivals and departures separately. Sweep: if the next arrival is ≤ the next departure, a platform is taken; otherwise one is freed.

Approach

Sort both lists and merge them like a timeline. If arr[i] <= dep[j], a train arrives before (or at the same minute as) the next departure: platforms++, i++. Otherwise a train leaves: platforms--, j++. Track the maximum. Using <= processes a same-minute arrival before the departure, which matches the rule that it needs a separate platform. Which train leaves doesn't matter, only how many trains are present.

Complexity: O(n log n) time · O(1) extra space

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n), dep(n);
    for (auto &x : arr) cin >> x;
    for (auto &x : dep) cin >> x;
    sort(arr.begin(), arr.end());
    sort(dep.begin(), dep.end());
    int i = 0, j = 0, cur = 0, best = 0;
    while (i < n) {
        if (arr[i] <= dep[j]) {
            cur++;
            i++;
            best = max(best, cur);
        } else {
            cur--;
            j++;
        }
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
arr = sorted(data[1 : n + 1])
dep = sorted(data[n + 1 : 2 * n + 1])
i = j = cur = best = 0
while i < n:
    if arr[i] <= dep[j]:
        cur += 1
        i += 1
        best = max(best, cur)
    else:
        cur -= 1
        j += 1
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n], dep = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        for (int i = 0; i < n; i++) dep[i] = sc.nextInt();
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i = 0, j = 0, cur = 0, best = 0;
        while (i < n) {
            if (arr[i] <= dep[j]) {
                cur++;
                i++;
                best = Math.max(best, cur);
            } else {
                cur--;
                j++;
            }
        }
        System.out.println(best);
    }
}

Solve Minimum Platforms online · All practice problems