How to Solve: Interval Scheduling / Merge Intervals

How to Solve: Interval Scheduling / Merge Intervals

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—nail it, and you prove you can handle real-world scheduling, resource allocation, and overlapping constraints with clarity and efficiency."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you’re comfortable with: 1. Sorting (custom comparators, stability, time complexity). 2. Greedy Algorithms (optimal substructure, making locally optimal choices). 3. Two-Pointer Technique (traversing sorted arrays efficiently).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental Checklist for Every Interval Problem:

1. Clarify the Problem
2. Are intervals sorted? If not, sort them.
3. What defines an overlap? (e.g., a.end >= b.start).

4. What’s the output? (Merged intervals? Max non-overlapping count? Insertion result?)

5. Sort Intervals

6. Sort by start time (default). If start times are equal, sort by end time.

7. Exception: For event-based problems (e.g., meeting rooms), sort all start/end points.

8. Initialize a Result Container

9. For merging: Start with the first interval.

10. For counting: Use a counter or a stack.

11. Iterate with a Pointer

12. Use a single pass (O(n)) to merge or count overlaps.

13. Compare the current interval with the next one to decide whether to merge, skip, or add.

14. Handle Edge Cases

15. Empty input.
16. Single interval.
17. All intervals overlapping.

18. Non-overlapping intervals.

19. Optimize for Follow-Ups

20. Can you do it in O(1) space? (Modify in-place.)
21. Can you handle dynamic updates? (Use a heap or binary search.)

? WORKED EXAMPLES

Example 1 – Basic: Merge Intervals

Problem: Given a list of intervals, merge all overlapping ones. Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]

Step-by-Step Solution

1. Sort by start time: [[1,3],[2,6],[8,10],[15,18]] (already sorted).
2. Initialize result = [intervals[0]].
3. Iterate from i = 1 to n-1:
4. If result[-1].end >= intervals[i].start, merge them (update result[-1].end).
5. Else, append intervals[i] to result.
6. Return result.

Code (Python)

def merge(intervals):

    if not intervals:

        return []


    intervals.sort(key=lambda x: x[0])

    result = [intervals[0]]


    for i in range(1, len(intervals)):

        last = result[-1]

        current = intervals[i]

        if last[1] >= current[0]:  # Overlap

            last[1] = max(last[1], current[1])  # Merge

        else:

            result.append(current)


    return result

Complexity

• Time: O(n log n) (sorting) + O(n) (merging) = O(n log n).
• Space: O(n) (for the result; O(1) if modified in-place).

Why This Works

• Sorting ensures we process intervals in order.
• Greedy merging guarantees we combine all overlapping intervals in a single pass.

Example 2 – Medium: Insert Interval

Problem: Insert a new interval into a list of non-overlapping intervals (already sorted by start time). Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

Step-by-Step Solution

1. Initialize result = [] and i = 0.
2. Add all intervals before the new interval (no overlap):
3. While intervals[i].end < newInterval.start, append intervals[i] to result and increment i.
4. Merge overlapping intervals:
5. While intervals[i].start <= newInterval.end, update newInterval to cover the merged range.
6. Add the merged interval to result.
7. Add remaining intervals to result.

Code (Python)

def insert(intervals, newInterval):

    result = []

    i = 0

    n = len(intervals)


    # Add all intervals before the newInterval

    while i < n and intervals[i][1] < newInterval[0]:

        result.append(intervals[i])

        i += 1


    # Merge overlapping intervals

    while i < n and intervals[i][0] <= newInterval[1]:

        newInterval[0] = min(newInterval[0], intervals[i][0])

        newInterval[1] = max(newInterval[1], intervals[i][1])

        i += 1

    result.append(newInterval)


    # Add remaining intervals

    while i < n:

        result.append(intervals[i])

        i += 1


    return result

Complexity

• Time: O(n) (single pass).
• Space: O(n) (for the result).

Why This Works

• The two-pointer approach efficiently separates non-overlapping intervals before/after the new interval.
• Merging in-place ensures we handle all overlaps in one pass.

Example 3 – Hard/Follow-Up: Meeting Rooms II

Problem: Given intervals representing meeting times, find the minimum number of rooms required. Input: [[0,30],[5,10],[15,20]] Output: 2 (Rooms needed: [0,30] and [5,10] overlap, [15,20] overlaps with [0,30].)

Step-by-Step Solution

1. Sort all start and end times separately.
2. Use two pointers (i for starts, j for ends) and a rooms counter.
3. If start[i] < end[j], a new room is needed (rooms++).
4. Else, a room is freed (j++).
5. Return rooms.

Code (Python)

def minMeetingRooms(intervals):

    if not intervals:

        return 0


    starts = sorted([i[0] for i in intervals])

    ends = sorted([i[1] for i in intervals])


    rooms = 0

    i = j = 0


    while i < len(intervals):

        if starts[i] < ends[j]:

            rooms += 1

            i += 1

        else:

            j += 1


    return rooms

Complexity

• Time: O(n log n) (sorting) + O(n) (sweep) = O(n log n).
• Space: O(n) (for storing starts/ends).

Why This Works

• The event-based sweep counts the maximum number of overlapping intervals at any point.
• Sorting start/end times allows us to simulate room allocation in linear time.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s your 60-second cheat sheet for interval problems: 1. Sort first—by start time, end time, or both (for event-based problems). 2. Use a single pass—merge, count, or insert with two pointers. 3. Handle overlaps—if current.end >= next.start, merge them. 4. Watch edge cases—empty input, single interval, all overlapping. 5. Optimize for follow-ups—think heaps for dynamic updates, binary search for insertion.

Interval problems test your ability to handle real-world constraints. Sort, sweep, and merge—you’ve got this!

? Final Notes

• Practice Problems:
• Merge Intervals (LeetCode 56)
• Insert Interval (LeetCode 57)
• Meeting Rooms II (LeetCode 253)
• Non-overlapping Intervals (LeetCode 435)
• Time Yourself: Aim for 10-15 minutes per problem in mock interviews.
• Whiteboard First: Sketch the sorted intervals and merging process before coding.

Now go crush that interview! ?