Interval Greedy: Sort by Start vs Sort by End
Timeline Merging vs Maximum Resource Scheduling
How sorting intervals by start time solves union and insertion problems, while sorting by end time solves maximum scheduling and minimum removal problems.
"Are you merging overlapping spans into unified blocks, or are you packing the maximum number of mutually compatible intervals into one resource?"
Ask this single question during the first two minutes of reading the problem prompt. The answer decides your fundamental pattern.
Consider a community auditorium in Koramangala, Bengaluru. The facility manager has two different tasks on two different days. On Monday, residents submit booking slots for birthday parties, meetings, and rehearsals. The manager wants to know: 'During which continuous blocks of time is the hall occupied so we can turn off the air conditioning during free gaps?' The manager sorts bookings by START time. That way, as each booking starts, you either extend the current occupied block or start a new one (Merge Intervals). On Friday, ten different college theatre groups request stage time on Sunday. The hall can host only one play at a time. The committee wants to maximize the number of plays staged. If you pick a play that starts at 9 AM and finishes at 6 PM, you waste the whole day on one play. Instead, you pick the play that FINISHES EARLIEST. Finishing early frees the auditorium for the next show as soon as possible (Interval Scheduling).
When to Choose Which Pattern
Sort by Start Time (interval[0])
Option A- ✓Merging overlapping intervals into a unified set of disjoint intervals (e.g. Merge Intervals).
- ✓Inserting a new interval and collapsing overlaps (e.g. Insert Interval).
- ✓Calculating total occupied or idle time across multiple events.
- ✓Determining minimum rooms required (e.g. Meeting Rooms II) when paired with a min-heap of end times.
Sort by End Time (interval[1])
Option B- ✓Maximizing the count of mutually compatible events (classic Interval Scheduling).
- ✓Finding the minimum number of intervals to remove to eliminate all overlaps (e.g. Non-overlapping Intervals).
- ✓Greedy choice rule: freeing the resource as early as possible leaves maximum opportunity for all future candidates.
- ✓Selecting non-conflicting meetings for a single conference room.
Side-by-Side Worked Examples
Compare concrete implementations side by side to see how the code structure diverges.
Merge Intervals(LC 56)
LeetCode ↗Sort intervals by start time. Initialize result with the first interval. For each subsequent interval, if its start is <= previous interval's end, merge them by setting prev.end = max(prev.end, curr.end). If its start is > previous end, there is a gap; push the current interval as a new disjoint block.
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
prev_end = merged[-1][1]
if start <= prev_end:
merged[-1][1] = max(prev_end, end)
else:
merged.append([start, end])
return mergedNon-overlapping Intervals(LC 435)
LeetCode ↗Sort intervals by end time. Keep track of the end time of the last accepted interval (prev_end). For each interval, if its start is < prev_end, it overlaps with an interval that finished earlier or equal: remove it (increments removal count). If its start >= prev_end, accept it and update prev_end = curr.end.
def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
intervals.sort(key=lambda x: x[1])
removals = 0
prev_end = float('-inf')
for start, end in intervals:
if start < prev_end:
removals += 1
else:
prev_end = end
return removalsThe Decision Matrix
Problem Goal
Union / consolidation of overlapping periods
Maximum selection / minimum removal of conflicting events
Greedy Invariant
Contiguous timeline continuity (no missed overlaps)
Earliest resource release (maximum room left)
Handling Overlaps
Expand previous end to max(prev.end, curr.end)
Discard the conflicting interval with the later finish
Multiple Resources
Meeting Rooms II: sort by start, track room free times in a min-heap
Single-resource greedy packing
| Evaluation Factor | Sort by Start Time (interval[0]) | Sort by End Time (interval[1]) |
|---|---|---|
| Problem Goal | Union / consolidation of overlapping periods | Maximum selection / minimum removal of conflicting events |
| Greedy Invariant | Contiguous timeline continuity (no missed overlaps) | Earliest resource release (maximum room left) |
| Handling Overlaps | Expand previous end to max(prev.end, curr.end) | Discard the conflicting interval with the later finish |
| Multiple Resources | Meeting Rooms II: sort by start, track room free times in a min-heap | Single-resource greedy packing |
Where Candidates Go Wrong (Top Traps)
Sorting Non-overlapping Intervals by start time
Forgetting max(prev.end, curr.end) when merging nested intervals
Confusion over touching endpoints (start == end)
Related Walkthroughs in our DSA Course
Explore step-by-step solutions with 4-language code flaps (Java, C#, TS, Python) and visual memory dry runs.
Insert Interval (Contiguous Interval Consolidation)
Non-overlapping Intervals (Earliest End Greedy)
Meeting Rooms II (Start Sort + Min-Heap Free Times)
"Sorting by start time organizes timeline continuity for merging contiguous blocks, but cannot optimize resource packing. Sorting by end time greedily maximizes independent task count, but cannot produce consolidated coverage blocks without additional passes."
Practice Real Indian Hiring Loops
See the exact problems asked at Flipkart, Swiggy, Razorpay, PhonePe, and Amazon with verified candidate reports and round structures.