A calendar application needs to schedule a new meeting from 2pm to 4pm against existing meetings from 1pm to 3pm and 3:30pm to 5pm. Does the new meeting conflict? How do you check this efficiently for hundreds of meetings?

This is an interval problem. Intervals appear everywhere in software: calendar systems, booking platforms, resource allocation, genomic data analysis, network packet scheduling, and database query optimization. Detecting overlaps, merging ranges, and finding gaps efficiently is a core skill.

Determining overlap correctly, handling edge cases, and doing it efficiently for thousands of intervals requires careful thinking. A few patterns cover most interval problems.

This chapter uses closed intervals [start, end] throughout. The overlap condition is a.start <= b.end && b.start <= a.end. For half-open [start, end) problems (common in scheduling APIs like Meeting Rooms II), replace <= with < so that meeting [1,5) does not conflict with [5,8).

An interval represents a continuous range with a start and end point. In coding problems, intervals are typically represented as arrays or objects with two values.

Intervals can be:

Most LeetCode problems use closed intervals [start, end], meaning both the start and end values are part of the interval.

Detecting Overlap

The most common interval question is whether two intervals overlap.

Given interval A = [a, b] and interval B = [c, d], they overlap if and only if:

This condition checks that A starts before B ends AND B starts before A ends. It is often easier to think about the negation: two intervals do NOT overlap if:

This means either A ends before B starts, or B ends before A starts.

The "touch at endpoint" case (where one interval ends exactly where another starts) frequently causes off-by-one bugs. Whether [1,5] and [5,8] are considered overlapping depends on whether the problem uses closed or half-open intervals. Read the problem statement carefully.

Sorting Strategies

Most interval algorithms begin with sorting. The two common approaches are:

Sort by start time: Used for merging intervals. After sorting, overlapping intervals become adjacent, making them easy to merge in a single pass.

Sort by end time: Used for interval selection problems (like activity selection). By always picking the interval that ends earliest, you leave maximum room for subsequent intervals. The exchange-argument proof: any optimal schedule can be transformed into the greedy one by swapping each interval with the earliest-ending compatible alternative without reducing the count.

Tie-Breaking in Sort Comparators

When intervals share start or end times, secondary sort order can change correctness.

Read the problem statement carefully for inclusive vs. exclusive endpoint semantics before writing the comparator.

Merging Two Intervals

When two intervals overlap, merging them creates a single interval:

The merged interval starts at whichever interval started earlier and ends at whichever ended later.

Problem: given a list of intervals, merge all overlapping intervals and return the result.

Approach

The merge step expands the last result interval's end to max(last.end, current.end). The end of the last interval can only grow, never shrink, so a single pass is enough.

Walkthrough

Trace on [[1,3],[2,6],[8,10],[15,18]]:

Final result: [[1,6],[8,10],[15,18]].

Implementation

Time Complexity: O(n log n) for the sort, O(n) for the merge pass. Total: O(n log n).

Space Complexity: O(n) for the output list. Auxiliary space is O(log n) for the sort on most implementations.

Problem: given a sorted, non-overlapping interval list and a new interval, insert the new interval and merge any resulting overlaps.

Approach

Walk through the input list in three phases:

Because the input is already sorted, a single pass is enough. No global sort is needed, so the work is linear in the input size.

Walkthrough

Trace on intervals = [[1,3],[6,9]], newInterval = [2,5]:

Final result: [[1,5],[6,9]].

Implementation

Time Complexity: O(n) since each input interval is visited once.

Space Complexity: O(n) for the output list.

Two related problems use the same input shape but answer different questions.

Meeting Rooms I (LC 252)

Problem: given an array of meeting time intervals, determine whether a single person can attend all meetings without conflicts.

Approach: sort by start time. For each consecutive pair, return false if the previous meeting's end is greater than the current meeting's start. Half-open semantics treat [1,5] and [5,8] as non-conflicting (the room frees at end time).

This is a building block. The harder cousin asks for the minimum number of rooms.

Meeting Rooms II (LC 253)

Problem: given an array of meeting time intervals, return the minimum number of conference rooms required to host all meetings.

Approach (min-heap by end time): sort intervals by start time. Maintain a min-heap of meeting end times. For each new meeting, check whether the earliest-ending meeting on the heap has already ended (its end time is at or before the new meeting's start). If yes, pop it (that room is now free). Push the new meeting's end time. The heap size at any moment equals the number of rooms currently in use, and the maximum heap size during the iteration is the answer. Because the heap can only shrink when a room is freed and only grows when a new meeting starts, its final size is also the maximum size reached.

Walkthrough

Trace on [[0,30],[5,10],[15,20]]:

Answer: 2 rooms.

Implementation

Time Complexity: O(n log n) for the sort plus O(n log n) for heap operations.

Space Complexity: O(n) for the heap in the worst case (all meetings concurrent).

Approach 2 (sweep line / chronological events): treat each meeting as two events, +1 at its start and -1 at its end. Sort the events by position, then sweep through them while tracking a running counter. The maximum value of the counter is the answer. This runs in O(n log n) with a different constant factor and shares the framework used by other interval problems (see the next section).

Sweep line is a general framework for interval problems. Convert each interval into two events (a start event and an end event), sort the events by position, and sweep through them while maintaining a running counter that tracks active intervals.

General Template

For Meeting Rooms II, the answer is the maximum counter value reached during the sweep. The sort by (position, delta) produces the correct tie-breaking for half-open intervals because -1 < +1.

Implementation

Other Sweep Line Applications

The same event-counter pattern solves several related problems:

The pattern is a useful mental tool when a problem asks "how many things are active at the busiest moment" or "what is the union/gap structure across many intervals".

Problem: given a list of intervals, return the minimum number of intervals to remove so that the remaining intervals are non-overlapping.

This is equivalent to the interval scheduling maximization problem: find the largest subset of intervals that do not overlap. The answer to the original problem is n - max_nonoverlapping.

Approach

Greedy by end time. Sort the intervals by end time. Iterate through the sorted list, greedily picking each interval whose start is greater than or equal to the last picked interval's end.

Exchange argument: any optimal schedule can be transformed into this greedy one without reducing the count, by swapping each picked interval with the earliest-ending compatible alternative. Picking the earliest-ending compatible interval leaves the most room for subsequent picks, which is why greedy-by-end is optimal here while greedy-by-start is not.

Walkthrough

Trace on [[1,2],[2,3],[3,4],[1,3]]:

Removed = 4 - 3 = 1.

Implementation

Time Complexity: O(n log n) for the sort, O(n) for the greedy pass.

Space Complexity: O(1) extra space beyond the input (O(log n) for the sort on most implementations).

Interval problems come in several flavors, each mapped to a sorting strategy and an approach.

Signs that you are facing an interval problem:

When these techniques might NOT apply:

This problem uses basic overlap detection. Meeting Rooms uses half-open semantics: meeting [1,5] does not conflict with [5,8] because the rooms are released at the end time. The code below uses strict < to match this convention.

Problem: Given an array of meeting time intervals where intervals[i] = [start, end], determine if a person can attend all meetings.

Approach

If any two meetings overlap, return false. The brute force approach checks all pairs in O(n^2). But if we sort by start time, overlapping meetings become adjacent. We only need to check each meeting against the previous one.

After sorting by start time, meeting A overlaps with meeting B (where A comes before B) if and only if A's end time is greater than B's start time.

Implementation

Walkthrough

Time Complexity: O(n log n) for sorting, O(n) for the scan. Total: O(n log n).

Space Complexity: O(1) extra space (O(log n) for sorting in some implementations).

This problem uses the two-pointer approach on two sorted interval lists.

Problem: Given two lists of closed intervals, each list is pairwise disjoint (no overlaps within a list) and sorted. Return the intersection of these two interval lists.

Approach

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

The intersection of [a,b] and [c,d] (when they overlap) is:

Implementation

Walkthrough

Time Complexity: O(m + n) where m and n are the lengths of the two lists.

Space Complexity: O(m + n) for the output. O(1) auxiliary space if the output array is not counted as extra space.

Mistake 1: Forgetting to Sort

Many interval algorithms require sorted input. Forgetting to sort leads to incorrect results.

Mistake 2: Using Wrong Sort Key

Sorting by start time and end time are not interchangeable.

Mistake 3: Off-by-One in Overlap Detection

The difference between < and <= matters for whether touching intervals count as overlapping.

Read the problem carefully to determine the expected behavior.

Mistake 4: Forgetting the Last Interval

When building a result list incrementally, the last interval is often added inside the loop only under certain conditions. Make sure to add it after the loop.

Mistake 5: Modifying Input Array

Some problems pass the input by reference and expect the original array to remain unchanged after the function returns. This matters when the same input is reused across multiple test calls or when other code holds references to it. Creating a copy before sorting avoids this issue.