Interval Problems

🗓️ Interval Problems: The Art of Managing Busy Schedules

The Story of Overlapping Meetings

Imagine you’re a busy party planner. You have lots of events happening at different times. Some overlap, some don’t. Your job? Keep everything organized so nothing gets messy!

Interval problems are exactly like this. An interval is just a time slot with a start and an end.

Meeting A: [1, 3]  → Starts at 1, ends at 3
Meeting B: [2, 5]  → Starts at 2, ends at 5

These two overlap because Meeting B starts before Meeting A ends!

🔀 1. Merge Intervals

The Problem

You have a bunch of time slots. Some overlap. Combine all overlapping ones into bigger slots.

The Analogy: Painting a Wall

Imagine painting a wall. You paint from inch 1 to 3. Then from inch 2 to 5. What did you actually paint? Inch 1 to 5! The overlapping parts merge into one.

How It Works

1. Sort all intervals by their start time
2. Compare each interval with the previous one
3. If they overlap → merge them
4. If they don’t overlap → keep both separate

Visual Flow

graph TD
    A["Sort by start time"] --> B{Does current overlap with last?}
    B -->|Yes| C["Extend the end time"]
    B -->|No| D["Add as new interval"]
    C --> E["Move to next"]
    D --> E
    E --> F{More intervals?}
    F -->|Yes| B
    F -->|No| G["Done!"]

Python Code

def merge(intervals):
    if not intervals:
        return []

    # Step 1: Sort by start
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for current in intervals[1:]:
        last = merged[-1]

        # Overlap check
        if current[0] <= last[1]:
            # Merge: extend the end
            last[1] = max(last[1], current[1])
        else:
            # No overlap: add new
            merged.append(current)

    return merged

Example

Input:  [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]

[1,3] and [2,6] overlap → merge into [1,6]!

➕ 2. Insert Interval

The Problem

You have sorted, non-overlapping intervals. Insert a new interval and merge if needed.

The Analogy: Adding a New Meeting

Your calendar is clean. No overlapping meetings. Now your boss adds a new meeting. It might overlap with existing ones. What do you do? Merge whatever overlaps!

How It Works

1. Add all intervals that end before new one starts
2. Merge all overlapping intervals with the new one
3. Add all intervals that start after new one ends

Visual Flow

graph TD
    A["Intervals before new"] --> B["Add to result"]
    C["Overlapping intervals"] --> D["Merge with new"]
    E["Intervals after new"] --> F["Add to result"]
    B --> D --> F --> G["Done!"]

Python Code

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)

    # Add all before
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Merge overlapping
    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 all after
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Example

Intervals: [[1,2], [3,5], [6,7], [8,10]]
New:       [4,8]
Output:    [[1,2], [3,10]]

[3,5], [6,7], [8,10] all overlap with [4,8] → merge into [3,10]!

❌ 3. Non-overlapping Intervals

The Problem

You have intervals. Remove the minimum number so the rest don’t overlap.

The Analogy: Canceling Meetings

Your schedule is a mess. Meetings overlap everywhere! You need to cancel the fewest meetings so there are no conflicts.

The Greedy Insight 💡

Always keep the interval that ends earliest! Why? It leaves more room for future intervals.

How It Works

1. Sort by end time
2. Track the end of the last kept interval
3. If next interval starts before current end → remove it
4. Otherwise → keep it

Visual Flow

graph TD
    A["Sort by END time"] --> B["Keep first interval"]
    B --> C{Next starts before current end?}
    C -->|Yes| D["Remove it - count++"]
    C -->|No| E["Keep it - update end"]
    D --> F{More intervals?}
    E --> F
    F -->|Yes| C
    F -->|No| G["Return count"]

Python Code

def eraseOverlapIntervals(intervals):
    if not intervals:
        return 0

    # Sort by end time!
    intervals.sort(key=lambda x: x[1])

    removals = 0
    current_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < current_end:
            # Overlap! Remove this one
            removals += 1
        else:
            # No overlap, update end
            current_end = intervals[i][1]

    return removals

Example

Input:  [[1,2], [2,3], [3,4], [1,3]]
Output: 1

Remove [1,3] because it overlaps with [1,2] and [2,3].

🚪 4. Meeting Rooms II

The Problem

You have meetings with start and end times. How many meeting rooms do you need so no meetings conflict?

The Analogy: Hotel Check-ins

Guests arrive and leave at different times. You need enough rooms so everyone has a place. When does the hotel need the most rooms? That’s your answer!

The Greedy Insight 💡

Track how many meetings are happening at the same time. The maximum is your answer!

How It Works

1. Separate start times and end times
2. Sort both lists
3. Walk through: meeting starts → +1 room, meeting ends → -1 room
4. Track the maximum

Visual Flow

graph TD
    A["Separate starts and ends"] --> B["Sort both"]
    B --> C["Two pointers: s and e"]
    C --> D{"starts[s] < ends[e]?"}
    D -->|Yes| E["Meeting starts: rooms++"]
    D -->|No| F["Meeting ends: rooms--"]
    E --> G["Update max rooms"]
    G --> H["Move pointer"]
    F --> H
    H --> I{More to process?}
    I -->|Yes| D
    I -->|No| J["Return max rooms"]

Python Code

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
    max_rooms = 0
    s = e = 0

    while s < len(intervals):
        if starts[s] < ends[e]:
            rooms += 1
            max_rooms = max(max_rooms, rooms)
            s += 1
        else:
            rooms -= 1
            e += 1

    return max_rooms

Example

Input:  [[0,30], [5,10], [15,20]]
Output: 2

At time 5, both [0,30] and [5,10] are happening → need 2 rooms!

🔗 5. Interval Intersection

The Problem

You have two lists of intervals. Both are sorted and non-overlapping within themselves. Find all overlapping parts between the two lists.

The Analogy: Common Free Time

Your calendar has free slots: [[0,2], [5,10], [13,23]] Your friend’s calendar: [[1,5], [8,12], [15,24]]

When can you both meet? Find the overlapping times!

The Greedy Insight 💡

Use two pointers. For each pair, check if they overlap. If yes, the intersection is:

• Start = max of both starts
• End = min of both ends

Move the pointer whose interval ends earlier.

Visual Flow

graph TD
    A["Two pointers: i and j"] --> B{Do intervals overlap?}
    B -->|Yes| C["Add intersection"]
    B -->|No| D["Skip"]
    C --> E{Which ends first?}
    D --> E
    E -->|List A| F["Move pointer i"]
    E -->|List B| G["Move pointer j"]
    F --> H{More intervals?}
    G --> H
    H -->|Yes| B
    H -->|No| I["Return result"]

Python Code

def intervalIntersection(A, B):
    result = []
    i = j = 0

    while i < len(A) and j < len(B):
        # Find overlap
        start = max(A[i][0], B[j][0])
        end = min(A[i][1], B[j][1])

        # Valid intersection?
        if start <= end:
            result.append([start, end])

        # Move pointer with smaller end
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1

    return result

Example

A: [[0,2], [5,10], [13,23], [24,25]]
B: [[1,5], [8,12], [15,24], [25,26]]

Output: [[1,2], [5,5], [8,10], [15,23], [24,24], [25,25]]

🎯 Key Takeaways

🧠 The Pattern

All interval problems follow this pattern:

1. Sort (usually by start or end)
2. Compare neighbors or use two pointers
3. Greedy choice: pick locally optimal decision

Remember: When in doubt, sort first. Then walk through and make smart choices!

🎉 You Did It!

You now understand the 5 classic interval problems. They all share the same DNA:

• Intervals are just start-end pairs
• Sorting is your best friend
• Greedy choices lead to optimal solutions

Go practice! The more you see these patterns, the faster you’ll spot them in interviews. 🚀