Interval Problems

Greedy Algorithms: Interval Problems

The Calendar Wizard Story

Imagine you’re a Calendar Wizard working at a busy community center. Every day, people come to you with their time slots—when they want to use the meeting rooms. Your job? Organize these times smartly so everyone gets their space without chaos.

This is exactly what Interval Problems are about! An interval is just a fancy word for a time slot with a start and an end.

Interval = [start, end]
Example: [9, 12] means "from 9 AM to 12 PM"

The greedy approach means: “Make the best choice right now, and keep going.” Like picking the ripest apple first!

1. Merge Intervals

The Problem

People give you overlapping time slots. Your job: combine them into clean, non-overlapping blocks.

The Story

Think of it like painting a fence. If someone paints from post 1 to 5, and another paints from post 3 to 8, together they’ve painted from 1 to 8. No need to say “1 to 5 AND 3 to 8”—just say “1 to 8”!

graph TD
    A["[1,3] and [2,6]"] --> B["They overlap!"]
    B --> C["Merge into [1,6]"]

How It Works

1. Sort all intervals by their start time
2. Look at each interval one by one
3. If it overlaps with the previous one, merge them
4. If not, keep it separate

JavaScript Code

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);

  const result = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const current = intervals[i];

    // Do they overlap?
    if (current[0] <= last[1]) {
      // Merge: extend the end
      last[1] = Math.max(last[1], current[1]);
    } else {
      // No overlap: add as new
      result.push(current);
    }
  }

  return result;
}

Example

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

• [1,3] and [2,6] overlap → merged to [1,6]
• [8,10] stands alone
• [15,18] stands alone

2. Insert Interval

The Problem

You have a sorted list of non-overlapping intervals. Now insert a new one and merge if needed.

The Story

Your calendar is perfectly organized. Then someone calls: “I need a slot from 4 to 8!” You must slide it in and fix any overlaps.

graph TD
    A["Existing: [1,2], [3,5], [6,9]"]
    B["Insert: [4,8]"]
    A --> C["[3,5] overlaps with [4,8]"]
    B --> C
    C --> D["[6,9] also overlaps!"]
    D --> E["Result: [1,2], [3,9]"]

How It Works

1. Add all intervals that come before the new one
2. Merge all intervals that overlap with the new one
3. Add all intervals that come after

JavaScript Code

function insertInterval(intervals, newInt) {
  const result = [];
  let i = 0;
  const n = intervals.length;

  // Add all intervals before newInt
  while (i < n && intervals[i][1] < newInt[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Merge overlapping intervals
  while (i < n && intervals[i][0] <= newInt[1]) {
    newInt[0] = Math.min(newInt[0], intervals[i][0]);
    newInt[1] = Math.max(newInt[1], intervals[i][1]);
    i++;
  }
  result.push(newInt);

  // Add remaining intervals
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

Example

Intervals: [[1,3], [6,9]]
New:       [2,5]
Output:    [[1,5], [6,9]]

• [1,3] overlaps with [2,5] → merged to [1,5]
• [6,9] stays as is

3. Non-overlapping Intervals

The Problem

Given intervals, find the minimum number to remove so the rest don’t overlap.

The Story

You’re a DJ with a playlist. Some songs overlap in time slots. What’s the fewest songs to skip so no two play at the same time?

graph TD
    A["Intervals: [1,2], [2,3], [3,4], [1,3]"]
    B["[1,3] overlaps with [1,2] and [2,3]"]
    A --> B
    B --> C["Remove [1,3]"]
    C --> D["Now: [1,2], [2,3], [3,4] - no overlaps!"]

The Greedy Trick

Always keep the interval that ends earliest. Why? The earlier it ends, the more room for others!

How It Works

1. Sort intervals by end time
2. Track the end of the last kept interval
3. If the next interval starts before that end, skip it
4. Otherwise, keep it and update the end

JavaScript Code

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

  // Sort by end time
  intervals.sort((a, b) => a[1] - b[1]);

  let count = 0;
  let lastEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < lastEnd) {
      // Overlap! Remove this one
      count++;
    } else {
      // No overlap, update end
      lastEnd = intervals[i][1];
    }
  }

  return count;
}

Example

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

Remove [1,3] because it overlaps with others.

4. Meeting Rooms II

The Problem

Given meeting times, find the minimum number of rooms needed so all meetings can happen.

The Story

You’re the building manager. Everyone wants meetings at the same time! How many conference rooms do you need so no meeting waits?

graph TD
    A["Meetings: [0,30], [5,10], [15,20]"]
    B["At time 5: Meeting 1 is happening"]
    C["At time 5: Meeting 2 starts too!"]
    B --> D["Need 2 rooms at time 5"]
    C --> D
    A --> B
    A --> C
    D --> E["Answer: 2 rooms minimum"]

The Clever Trick

Separate start times and end times. Walk through time:

• Meeting starts? Need one more room
• Meeting ends? Free up one room

Track the maximum rooms needed at any point.

JavaScript Code

function minMeetingRooms(intervals) {
  const starts = intervals.map(i => i[0]).sort((a,b) => a-b);
  const ends = intervals.map(i => i[1]).sort((a,b) => a-b);

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

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

  return maxRooms;
}

Example

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

At time 5: Meeting [0,30] ongoing + [5,10] starts = 2 rooms
At time 10: [5,10] ends, only 1 room needed
At time 15: [15,20] starts, still 2 rooms max

5. Interval Intersection

The Problem

Given two lists of intervals, find where they overlap.

The Story

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

graph TD
    A["Your slots: [0,2], [5,10]"]
    B["Friend's: [1,5], [8,12]"]
    A --> C["Where do they overlap?"]
    B --> C
    C --> D["[1,2] and [8,10]"]

The Two-Pointer Dance

Use two pointers, one for each list. At each step:

1. Find if the current intervals overlap
2. If yes, record the intersection
3. Move the pointer for the interval that ends first

JavaScript Code

function intervalIntersection(A, B) {
  const result = [];
  let i = 0, j = 0;

  while (i < A.length && j < B.length) {
    // Find overlap boundaries
    const start = Math.max(A[i][0], B[j][0]);
    const end = Math.min(A[i][1], B[j][1]);

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

    // Move pointer of interval that ends first
    if (A[i][1] < B[j][1]) {
      i++;
    } else {
      j++;
    }
  }

  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]]

• [0,2] and [1,5] → overlap at [1,2]
• [5,10] and [1,5] → overlap at [5,5] (just the point!)
• [5,10] and [8,12] → overlap at [8,10]
• …and so on

The Big Picture

Why Greedy Works Here

In all these problems, we make local optimal choices:

• Sort first (usually by start or end time)
• Process one by one
• Make the best decision for right now
• Trust that this leads to the global best answer

It’s like organizing your closet: handle one item at a time, put it in the right place, and you’ll end up with a perfectly organized closet!

You’ve Got This!

You now understand the Calendar Wizard’s toolkit for interval problems:

1. Merge overlapping times into clean blocks
2. Insert new slots smoothly
3. Minimize removals for non-overlap
4. Count rooms for simultaneous meetings
5. Find common free times with friends

Each problem uses the same core idea: sort, scan, decide greedily. Practice each one, and you’ll handle any scheduling problem like a pro!