Intervals

Step 1 Understand it

Remember it by

Sort by start, then compare each interval with the last one you kept.

Watch it happen

The idea

Interval problems almost always start by sorting. After sorting by start, two intervals overlap exactly when the next one starts before the last one ends. Then merge, count or remove as the problem asks.

Picture it

flowchart LR
  S["sort by start"] --> N["next interval"]
  N --> Q{"start ≤ end of<br/>the last kept?"}
  Q -->|"yes"| M["merge: end = max(both ends)"]
  Q -->|"no"| A["append it"]
  M & A --> N

Analogy

Putting meetings on a calendar in time order. You only need to compare each meeting with the one just before it to spot a clash.

Where the analogy breaks

A calendar shows everything at a glance. In code, only the sort makes 'compare with the last one' enough; without it you'd have to compare every pair.

Step 2 Recognise it

Words that signal it

• Input is a list of [start, end] pairs
• 'Merge overlapping', 'insert an interval'
• 'Can a person attend all meetings?', 'minimum rooms'
• 'Remove the fewest intervals so none overlap'

Don't confuse it with

• Greedy: Non-overlapping Intervals is greedy: sort by END and keep whichever finishes first.
• Heap: Meeting Rooms II needs how many overlap at once: a min-heap of end times, or sorted starts and ends with two pointers.

Gut check

Pairs of [start, end]? → sort them first, then compare with the last one kept.

How to recognise it in an interview

Input is an array of pairs representing [start, end] ranges.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])     # 1. sort by start
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:                 # 2. overlaps the last one kept
            last[1] = max(last[1], end)      #    extend it
        else:
            merged.append([start, end])      # 3. no overlap: keep it
    return merged

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        // Step 1: Sort by starting time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        List<int[]> result = new ArrayList<>();
        int[] currentInterval = intervals[0];
        result.add(currentInterval);
        
        // Step 2: Iterate and check for overlaps
        for (int[] interval : intervals) {
            int currentEnd = currentInterval[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];
            
            if (nextStart <= currentEnd) { // Overlap detected!
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else { // No overlap
                currentInterval = interval;
                result.add(currentInterval);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

Common mistakes

• Forgetting to sort first.
• Getting the touching case wrong: does [1, 2] overlap [2, 3]? Read the problem.
• When merging, setting end = new end instead of max(old end, new end).
• Trying to merge arrays blindly without updating the reference pointer correctly in Java.

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

def can_attend_meetings(intervals):
    intervals.sort()
    for (s1, e1), (s2, e2) in zip(intervals, intervals[1:]):
        if s2 < e1:
            return False
    return True

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = [intervals[0][:]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

1. Mark "Meeting Rooms" as solved Meeting Rooms Easy

   Decide whether one person can attend all meetings.

   Show answer

   Technique: Sort + check neighbours

   The clue: Any overlap at all.

   The trick: Sort by start; if any meeting starts before the previous one ends, return false.

Medium

1. Mark "Insert Interval" as solved Insert Interval Medium

   Insert a new interval into a sorted list of non-overlapping intervals, merging where needed.

   Show answer

   Technique: Intervals: before, overlap, after

   The clue: Already sorted intervals plus one new one.

   The trick: Add the intervals that end before it, merge all that overlap it, then add the rest.

2. Mark "Merge Intervals" as solved Merge Intervals Medium

   Merge all overlapping intervals.

   Show answer

   Technique: Sort by start + merge

   The clue: 'Merge overlapping'.

   The trick: Sort by start; extend the last kept interval or start a new one.

3. Mark "Non Overlapping Intervals" as solved Non Overlapping Intervals Medium

   Remove the fewest intervals so the rest don't overlap.

   Show answer

   Technique: Greedy: sort by end

   The clue: Keep as many as possible without overlaps.

   The trick: Sort by end and keep each interval that starts after the last kept one ends; count the rest as removed.

4. Mark "Meeting Rooms II" as solved Meeting Rooms II Medium

   Find the minimum number of rooms needed for all meetings.

   Show answer

   Technique: Min-heap of end times (or sorted starts and ends)

   The clue: The most meetings happening at the same time.

   The trick: Sort by start; a min-heap holds end times of running meetings; reuse a room when the earliest end ≤ the new start.

Hard

1. Mark "Minimum Interval to Include Each Query" as solved Minimum Interval to Include Each Query Hard

   For each query point, find the size of the smallest interval that contains it.

   Show answer

   Technique: Sort queries + min-heap

   The clue: Many point queries against many intervals.

   The trick: Sort intervals and queries; for each query push intervals that start ≤ q into a heap by size and pop those that end before q.

What to say in the interview

'Because we need to identify overlapping sets, I will first sort the intervals by their start times to guarantee a linear left-to-right sweep.'

Follow-up prep

Can you solve this if you are given a stream of intervals one by one? (Hint: Use a TreeMap).