Interval Problems

🗓️ The Calendar Wizard: Mastering Interval Problems

Imagine you’re a magical calendar wizard. People come to you with messy schedules full of overlapping meetings, and you make them perfect. That’s what interval problems are all about!

🎯 What Are Intervals?

Think of an interval as a time slot on your calendar:

• Start time → When something begins
• End time → When something ends

int[] meeting = {9, 10};  // Starts at 9, ends at 10

An interval is just a pair: [start, end]

Real Life Examples:

• 🎬 Movie showing: [2:00 PM, 4:00 PM]
• 📚 Class period: [9:00, 10:30]
• 🏥 Doctor appointment: [3:15, 3:45]

🧙‍♂️ The Greedy Magic Trick

Greedy means: “Make the best choice RIGHT NOW, don’t worry about later.”

Like eating candy:

• A greedy child eats the BIGGEST candy first
• Then the next biggest
• And so on…

For intervals, we usually sort first, then make simple decisions one by one!

1️⃣ Merge Intervals

📖 The Story

Imagine your calendar looks like a mess:

• Meeting A: 9:00 - 11:00
• Meeting B: 10:00 - 12:00
• Meeting C: 1:00 - 2:00

Wait… A and B overlap! You’re double-booked from 10-11!

Merge Intervals combines overlapping meetings into one big block.

🎯 The Pattern

Before: [9,11] [10,12] [1,2]
After:  [9,12] [1,2]

The overlapping ones become ONE!

🔮 The Magic Steps

1. Sort all intervals by start time
2. Look at each one - does it overlap with the previous?
3. If yes → merge them (extend the end time)
4. If no → start a new merged interval

💻 Java Code

public int[][] merge(int[][] intervals) {
    // Step 1: Sort by start time
    Arrays.sort(intervals,
        (a, b) -> a[0] - b[0]);

    List<int[]> result = new ArrayList<>();
    int[] current = intervals[0];

    for (int i = 1; i < intervals.length; i++) {
        // Does next interval overlap?
        if (intervals[i][0] <= current[1]) {
            // Yes! Extend the end time
            current[1] = Math.max(
                current[1], intervals[i][1]);
        } else {
            // No overlap - save & start new
            result.add(current);
            current = intervals[i];
        }
    }
    result.add(current);
    return result.toArray(new int[0][]);
}

🎨 Visual Example

graph TD
    A["[1,3] [2,6] [8,10] [15,18]"] --> B["Sort by start"]
    B --> C["[1,3] overlaps [2,6]?"]
    C -->|"3 >= 2 ✓"| D["Merge → [1,6]"]
    D --> E["[1,6] overlaps [8,10]?"]
    E -->|"6 < 8 ✗"| F["Keep separate"]
    F --> G["Result: [1,6] [8,10] [15,18]"]

🧠 Key Insight

Two intervals overlap if: intervalA.end >= intervalB.start

2️⃣ Insert Interval

📖 The Story

Your calendar is perfectly organized. Then your boss says:

“Squeeze in this new meeting!”

Now you need to:

1. Find where it goes
2. Merge with any overlapping meetings
3. Keep everything sorted!

🎯 The Pattern

Existing: [1,3] [6,9]
New:      [2,5]
Result:   [1,5] [6,9]

The new interval [2,5] overlapped with [1,3] and merged!

🔮 The Magic Steps

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

💻 Java Code

public int[][] insert(
    int[][] intervals, int[] newInterval) {

    List<int[]> result = new ArrayList<>();
    int i = 0;

    // Part 1: Add all before
    while (i < intervals.length &&
           intervals[i][1] < newInterval[0]) {
        result.add(intervals[i++]);
    }

    // Part 2: Merge overlapping
    while (i < intervals.length &&
           intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(
            newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(
            newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);

    // Part 3: Add all after
    while (i < intervals.length) {
        result.add(intervals[i++]);
    }

    return result.toArray(new int[0][]);
}

🎨 Visual Flow

graph TD
    A["Existing: [1,2] [3,5] [6,7] [8,10]"] --> B["Insert: [4,8]"]
    B --> C["Before [4,8]: [1,2]"]
    C --> D["Overlaps: [3,5] [6,7] [8,10]"]
    D --> E["Merge all → [3,10]"]
    E --> F["Result: [1,2] [3,10]"]

3️⃣ Non-Overlapping Intervals

📖 The Story

You have TOO MANY meetings and they overlap!

Your goal: Remove the MINIMUM number of meetings so nothing overlaps anymore.

It’s like cleaning your room - throw away the least stuff to make it tidy!

🎯 The Pattern

Input:  [1,2] [2,3] [3,4] [1,3]
Remove: [1,3] (it overlaps with both!)
Output: 1 (we removed 1 interval)

🔮 The Greedy Trick

Always keep the interval that ENDS EARLIEST!

Why? Because it leaves MORE room for future intervals!

Think of it like parking cars:

• A short car leaves more space for others
• So always pick the “short” (early-ending) interval!

💻 Java Code

public int eraseOverlapIntervals(int[][] intervals) {
    // Sort by END time (greedy choice!)
    Arrays.sort(intervals,
        (a, b) -> a[1] - b[1]);

    int removals = 0;
    int lastEnd = Integer.MIN_VALUE;

    for (int[] interval : intervals) {
        if (interval[0] >= lastEnd) {
            // No overlap - keep it!
            lastEnd = interval[1];
        } else {
            // Overlap - remove this one
            removals++;
        }
    }
    return removals;
}

🧠 Key Insight

Sort by END time, not start time!

Keeping early-ending intervals = maximum room for others

4️⃣ Meeting Rooms II

📖 The Story

You’re booking meeting rooms for a company. Everyone has meetings at different times.

Question: What’s the MINIMUM number of rooms needed so no one is left waiting?

It’s like figuring out how many checkout lanes a store needs at peak hours!

🎯 The Pattern

Meetings: [0,30] [5,10] [15,20]
          ├──────────────────┤ Room 1
               ├──┤           Room 2
                    ├───┤     Room 1 (reused!)
Answer: 2 rooms needed

🔮 The Magic Steps

Sweep Line Technique:

1. Mark all start times as +1 (someone enters)
2. Mark all end times as -1 (someone leaves)
3. Walk through time, tracking the count
4. The maximum count = rooms needed!

💻 Java Code

public int minMeetingRooms(int[][] intervals) {
    int[] starts = new int[intervals.length];
    int[] ends = new int[intervals.length];

    for (int i = 0; i < intervals.length; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }

    Arrays.sort(starts);
    Arrays.sort(ends);

    int rooms = 0, maxRooms = 0;
    int s = 0, e = 0;

    while (s < starts.length) {
        if (starts[s] < ends[e]) {
            // New meeting starts
            rooms++;
            maxRooms = Math.max(maxRooms, rooms);
            s++;
        } else {
            // A meeting ended
            rooms--;
            e++;
        }
    }
    return maxRooms;
}

🎨 Timeline View

graph TD
    A["Time 0: Meeting starts → 1 room"] --> B["Time 5: Another starts → 2 rooms"]
    B --> C["Time 10: One ends → 1 room"]
    C --> D["Time 15: One starts → 2 rooms"]
    D --> E["Time 20: One ends → 1 room"]
    E --> F["Max was 2 → Answer: 2 rooms"]

🧠 Key Insight

Separate starts and ends, sort them, sweep through time!

5️⃣ Interval Intersection

📖 The Story

You and your friend both have busy schedules. You want to find when you’re BOTH free to hang out!

Intersection = times that exist in BOTH schedules.

🎯 The Pattern

Your free times:   [0,2] [5,10] [13,23]
Friend's free:     [1,5] [8,12] [15,24]

Both free:         [1,2] [5,5] [8,10] [15,23]

🔮 The Magic Steps

1. Use two pointers (one for each list)
2. Find the overlap between current intervals
3. Move the pointer with the earlier ending interval
4. Repeat until done!

💻 Java Code

public int[][] intervalIntersection(
    int[][] firstList, int[][] secondList) {

    List<int[]> result = new ArrayList<>();
    int i = 0, j = 0;

    while (i < firstList.length &&
           j < secondList.length) {

        // Find overlap
        int start = Math.max(
            firstList[i][0], secondList[j][0]);
        int end = Math.min(
            firstList[i][1], secondList[j][1]);

        // Valid overlap?
        if (start <= end) {
            result.add(new int[]{start, end});
        }

        // Move pointer with earlier end
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result.toArray(new int[0][]);
}

🎨 Visual Overlap

graph TD
    A["A: [0,2]  B: [1,5]"] --> B["Overlap: max#40;0,1#41;=1 to min#40;2,5#41;=2"]
    B --> C["Result: [1,2] ✓"]
    C --> D["A ends first → move A pointer"]
    D --> E["A: [5,10]  B: [1,5]"]
    E --> F["Overlap: [5,5] ✓"]

🧠 Key Insight

Overlap exists when: max(start1, start2) <= min(end1, end2)

🎓 Summary: The Interval Toolkit

🚀 You’re Now an Interval Wizard!

Remember the magic formula:

1. Sort (usually by start or end)
2. Sweep through one by one
3. Make greedy decisions at each step

These 5 patterns will solve 90% of interval problems you’ll ever see!

“The calendar wizard doesn’t predict the future. They simply organize the present, one interval at a time.”

🎉 Happy Coding!