Intervals

Reach for it when

• Merge, insert, or count overlapping ranges
• Meeting rooms / minimum resources at the same time
• Remove the fewest intervals to avoid overlap

Core idea

After sorting by start, an interval overlaps the previous merged one exactly when its start is at most the current end. For 'how many at once', sweep sorted start and end events or keep a min-heap of end times. For 'fewest removals', sort by end and greedily keep the interval that finishes first.

Template · O(n log n) time for the sort, O(n) output

def merge(intervals):
    intervals.sort()
    out = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= out[-1][1]:              # overlaps
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

vector<vector<int>> merge(vector<vector<int>> intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> out{intervals[0]};
    for (size_t i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] <= out.back()[1])            // overlaps
            out.back()[1] = max(out.back()[1], intervals[i][1]);
        else
            out.push_back(intervals[i]);
    }
    return out;
}

Common pitfalls

• Touching endpoints: decide whether [1,2] and [2,3] overlap
• Taking end = e instead of max(end, e) when merging

Practice · 0 / 6 done

• Meeting RoomsEasy
• Insert IntervalMedium
• Meeting Rooms IIMedium
• Merge IntervalsMedium
• Non Overlapping IntervalsMedium
• Minimum Interval to Include Each QueryHard