What is the brute force approach and complexity for Minimum Platforms?

For each arrival time, count the trains at the station at that minute with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Minimum Platforms?

Two sorted lists; at station = arrived − left, with left counting only dep < arr with optimal time complexity O(N log N) and space complexity O(1).

Minimum Platforms

Q: How do you identify the pattern for Minimum Platforms?

Look for key signals in the prompt: "minimum number of platforms" indicates = the most trains at the station at the same moment (same as rooms).; "arrival and departure times" indicates Intervals as two separate arrays → sort each and sweep with two pointers.; "a train leaving and one arriving at the same minute both need a platform" indicates Inclusive times: on a tie, count the arrival BEFORE the departure (`dep[j] < arr[i]`)..

Medium·GeeksforGeeks Pro OnlyPattern Transfer

GeeksforGeeks

Problem Statement

Train i arrives at a station at time arr[i] and leaves at time dep[i]. Times are written as 24-hour HHMM numbers, e.g. 950 is 9:50 and 1120 is 11:20. All trains arrive and leave on the same day.

A train occupies a platform from its arrival minute to its departure minute, both included. So if one train leaves at 1120 and another arrives at 1120, both are at the station at 1120 and they need different platforms.

Implement int findPlatform(vector<int>& arr, vector<int>& dep) that returns the smallest number of platforms so that no train ever has to wait.

Input

Two arrays of the same length: arr (arrival times) and dep (departure times). arr[i] ≤ dep[i].

Output

One integer: the minimum number of platforms.

Example 1

Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]

Output: 3

Around 11:00, the trains of 940–1200, 950–1120 and 1100–1130 are all at the station at once.

Example 2

Input: arr = [900, 1235, 1100], dep = [1000, 1240, 1200]

Output: 1

No two trains are at the station at the same time, so one platform is enough.

Example 3

Input: arr = [900, 1000], dep = [1000, 1100]

Output: 2

At 1000 the first train is still at its platform (it leaves at 1000) while the second one arrives. Times are inclusive, so they need two platforms.

Constraints

• 1 ≤ n ≤ 5 · 10^4
• 0000 ≤ arr[i] ≤ dep[i] ≤ 2359
• arr and dep are not necessarily sorted

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimum number of platforms”

→ = the most trains at the station at the same moment (same as rooms).

“arrival and departure times”

→ Intervals as two separate arrays → sort each and sweep with two pointers.

“a train leaving and one arriving at the same minute both need a platform”

→ Inclusive times: on a tie, count the arrival BEFORE the departure (`dep[j] < arr[i]`).

Approach Complexity Ladder

Brute Force — count at every arrivalO(N²)O(1)

For each arrival time, count the trains at the station at that minute

Optimal — sort arrivals and departures, sweepO(N log N)O(1)

Two sorted lists; at station = arrived − left, with left counting only dep < arr

Brute Force Intuition

The answer is the most trains at the station at once, and that count only rises at an arrival. So for each train i, count trains j with arr[j] ≤ arr[i] ≤ dep[j] (arrived, and not yet left, inclusive). Return the biggest count.

Recognition rule for this sub-pattern:

How many things are active at the same time? Sweep events in time order, or keep a min-heap of end times.

Remember this · Intervals

Trigger

Input is [start, end] pairs; overlap, merge, insert, meeting rooms, free time, minimum removals.

Think

After sorting, do I only ever need to compare against the most recent interval?

Key question

Sort by start or by end — which one makes the greedy choice obvious?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Intervals translate into production architectures and low-level memory mechanics.

LLD Architecture