📅

Sort + Greedy — Interval Scheduling

Sort the events, then greedily scan with a pointer or counter. Sorting eliminates the need to look back — each decision only depends on the current event and the best previous outcome.

📅 Sort First ↔️ Two-Pointer 🔗 Merge / Count Time O(n log n) Space O(1)

📋 When to Use

Minimum Platforms / Meeting Rooms: sort arrivals and departures separately; two-pointer sweep counts overlap
Interval Merging: sort by start; merge when next.start <= prev.end
Activity Selection: sort by end time; greedily take earliest-ending non-overlapping activity
After sorting, each step is O(1) — the greedy choice is always locally optimal

💡 Sort once — then a single linear sweep is all you need. The sorted order guarantees we never need to revisit earlier events.

⚡ Complexity

Sorting

O(n log n)

Sweep / Merge

O(n)

Sorting: O(n log n) — dominates the overall complexity.
Sweep / merge: O(n) — one pass through sorted data.
Space: O(1) extra for pointer sweep; O(n) if building merged output list.

Problem Given train schedules with arrivals = [1,2,3,5] and departures = [4,6,7,8], find the minimum platforms needed so no train waits (GFG). Also: given intervals [[1,4],[2,6],[8,10],[15,18]], merge all overlapping ones (LC #56). Both use the same greedy sort idea — process events in order and make the locally optimal choice.
Input (Platforms): arr = [1,2,3,5], dep = [4,6,7,8] · Answer: 3 platforms · Merge: [[1,4],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

Step 0 / 5

🔧 Init 🟡 Arrival 🔵 Departure ✅ Done

// initializing...

Arrivals [ ]

Departures [ ]

Compare: arr[i]=— vs dep[j]=—

Platforms Now

Max Platforms

        i = 1
          
        j = 0

🚂 Train Timeline (Gantt)

📊 Interval Timeline (0 – 20) Current = yellow highlight

Merged Output:

[ waiting... ]

🧩 Pattern Skeleton Java 8

// ─── Minimum Platforms (sort arr + dep, two-pointer) ─────
Arrays.sort(arr);  Arrays.sort(dep);
int platforms = 1, maxP = 1, i = 1, j = 0;
while (i < n && j < n) {
    if (arr[i] <= dep[j]) { platforms++; i++; }   // arrival
    else                  { platforms--; j++; }   // departure
    maxP = Math.max(maxP, platforms);
}
return maxP;

// ─── Merge Intervals ──────────────────────────────────────
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);   // sort by start
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);
for (int[] curr : intervals) {
    int[] last = merged.get(merged.size() - 1);
    if (curr[0] <= last[1])                       // overlap
        last[1] = Math.max(last[1], curr[1]);     // extend
    else
        merged.add(curr);                         // new interval
}

🎯 Practice Problems

GFG Minimum Platforms 📅 arrival/departure sweep Medium #56 Merge Intervals 🔗 sort by start, merge Medium #57 Insert Interval 🔗 merge after insert Medium #435 Non-overlapping Intervals 📅 activity selection / sort by end Medium #253 Meeting Rooms II 📅 min meeting rooms (two-pointer) Medium #134 Gas Station ↔️ circular greedy Medium #135 Candy ↔️ two-pass greedy Hard