Interval Problems - Data Structures & Algorithms

Interval problems show up constantly in interviews. They’re their own category because the same core trick keeps appearing: sort by start time, then process one by one while tracking overlaps.

In simple language, think of scheduling meetings. Each meeting has a start and end time. We need to figure out things like “do any meetings overlap?” or “how many rooms do we need?” These are all interval problems.

When Do Two Intervals Overlap?

This is the foundation. Two intervals [a, b] and [c, d] overlap if and only if a < d AND c < b. But it’s easier to check the opposite — they DON’T overlap when one ends before the other starts.

Interval Overlap Visualization

Overlapping

Merged result: [1, 7]

Not Overlapping

No merge needed. They stay separate.

Merge Intervals

Given a collection of intervals, merge all overlapping ones (LeetCode #56). This is the bread and butter of interval problems.

Strategy: Sort by start time. Then walk through, extending the current interval if there’s overlap, or starting a new one if there’s a gap.

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]); // sort by start
  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      // overlapping -- extend the end
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      // no overlap -- start a new interval
      merged.push(intervals[i]);
    }
  }
  return merged;
}
// merge([[1,3],[2,6],[8,10],[15,18]])
// => [[1,6],[8,10],[15,18]]

def merge(intervals):
    intervals.sort(key=lambda x: x[0])  # sort by start
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            # overlapping -- extend the end
            last[1] = max(last[1], end)
        else:
            # no overlap -- start a new interval
            merged.append([start, end])
    return merged

# merge([[1,3],[2,6],[8,10],[15,18]])
# => [[1,6],[8,10],[15,18]]

static int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // sort by start
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0]);

    for (int i = 1; i < intervals.length; i++) {
        int[] last = merged.get(merged.size() - 1);
        if (intervals[i][0] <= last[1]) {
            last[1] = Math.max(last[1], intervals[i][1]); // extend
        } else {
            merged.add(intervals[i]); // new interval
        }
    }
    return merged.toArray(new int[0][]);
}

Time: O(n log n) for sorting. The merge pass is O(n). Space: O(n) for the result.

Insert Interval

Given sorted, non-overlapping intervals and a new interval, insert it and merge if needed (LeetCode #57).

Strategy: Three phases — add intervals that come entirely before the new one, merge all overlapping intervals with the new one, add intervals that come entirely after.

function insert(intervals, newInterval) {
  const result = [];
  let i = 0;

  // Phase 1: add all intervals ending before new one starts
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i++]);
  }
  // Phase 2: merge overlapping intervals
  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.push(newInterval);
  // Phase 3: add remaining intervals
  while (i < intervals.length) {
    result.push(intervals[i++]);
  }
  return result;
}

def insert(intervals, new_interval):
    result = []
    i = 0

    # Phase 1: add all intervals ending before new one starts
    while i < len(intervals) and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1
    # Phase 2: merge overlapping intervals
    while i < len(intervals) and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)
    # Phase 3: add remaining intervals
    result.extend(intervals[i:])
    return result

static int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0;

    // Phase 1: before overlap
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i++]);
    }
    // Phase 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);
    // Phase 3: after overlap
    while (i < intervals.length) result.add(intervals[i++]);
    return result.toArray(new int[0][]);
}

Time: O(n), Space: O(n). No sorting needed since input is already sorted.

Meeting Rooms I: Can We Attend All?

Given an array of meeting time intervals, determine if a person can attend all meetings (no overlaps). LeetCode #252.

This one’s straightforward. Sort by start time, then check if any meeting starts before the previous one ends.

function canAttendMeetings(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i - 1][1]) {
      return false; // overlap found
    }
  }
  return true;
}
// canAttendMeetings([[0,30],[5,10],[15,20]]) => false
// canAttendMeetings([[7,10],[2,4]]) => true

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False  # overlap found
    return True

# can_attend_meetings([[0,30],[5,10],[15,20]]) => False

static boolean canAttendMeetings(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false; // overlap found
        }
    }
    return true;
}

Time: O(n log n), Space: O(1) (ignoring sort space).

Meeting Rooms II: Minimum Rooms Needed

Now the harder version. Given meeting times, find the minimum number of conference rooms required (LeetCode #253).

Strategy: Use the sweep line technique. Separate starts and ends. Sort them. Walk through events: a start means +1 room needed, an end means -1 room freed. The peak is our answer.

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, maxRooms = 0, s = 0, e = 0;
  while (s < starts.length) {
    if (starts[s] < ends[e]) {
      rooms++;    // new meeting starts before earliest end
      s++;
    } else {
      rooms--;    // a meeting ended, free a room
      e++;
    }
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}
// minMeetingRooms([[0,30],[5,10],[15,20]]) => 2

def min_meeting_rooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)

    rooms = max_rooms = 0
    s = e = 0
    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1  # new meeting starts before earliest end
            s += 1
        else:
            rooms -= 1  # a meeting ended, free a room
            e += 1
        max_rooms = max(max_rooms, rooms)
    return max_rooms

# min_meeting_rooms([[0,30],[5,10],[15,20]]) => 2

static 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, s = 0, e = 0;
    while (s < starts.length) {
        if (starts[s] < ends[e]) {
            rooms++;
            s++;
        } else {
            rooms--;
            e++;
        }
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}

Time: O(n log n), Space: O(n) for the sorted arrays.

The Sweep Line Technique

Meeting Rooms II uses the sweep line — a powerful general technique. The idea is:

Break each interval into two events: a start (+1) and an end (-1)
Sort all events by time
Walk through events, maintaining a running count
The maximum count at any point is our answer

Sweep Line: Meetings [[0,30], [5,10], [15,20]]

t=0 +1 start rooms = 1

t=5 +1 start rooms = 2 (peak!)

t=10 -1 end rooms = 1

t=15 +1 start rooms = 2 (peak!)

t=20 -1 end rooms = 1

t=30 -1 end rooms = 0

Answer: 2 rooms needed (the peak concurrent count).

Sweep line works for a lot more than meeting rooms. Any problem asking “what’s the maximum overlap?” or “how many things are active at the same time?” is a sweep line candidate.

Interval Problem Cheatsheet

Problem	Key Trick	Complexity
Merge Intervals	Sort by start, extend end	O(n log n)
Insert Interval	Three-phase scan	O(n)
Meeting Rooms I	Sort, check adjacent overlaps	O(n log n)
Meeting Rooms II	Sweep line (separate starts/ends)	O(n log n)
Non-overlapping Intervals	Sort by end, greedy count	O(n log n)
Interval List Intersection	Two pointers on sorted lists	O(n + m)

The golden rule for interval problems: sort first, then process linearly. Almost every interval problem starts with sorting by start time (or end time for greedy selection). Once sorted, the overlaps become obvious to handle.