Imagine you are building a calendar application. A user wants to schedule a meeting from 2pm to 4pm, but they already have meetings from 1pm to 3pm and from 3:30pm to 5pm. Does the new meeting conflict with existing ones? How would you check this efficiently if the user has 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. The ability to efficiently detect overlaps, merge ranges, and find gaps is fundamental.

What makes interval problems interesting is that they look deceptively simple. Two intervals either overlap or they do not, right?

But determining this correctly, handling edge cases, and doing it efficiently for thousands of intervals requires careful thinking. Fortunately, a few key patterns cover most interval problems you will encounter.

What Is an Interval?

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.

Core Concepts

Before diving into specific problems, let us establish the fundamental operations you need to master.

Detecting Overlap

The most common question is: do 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) is often a source of bugs. Whether [1,5] and [5,8] are considered overlapping depends on the problem definition. 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.

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 Variants

Interval problems come in several flavors. Recognizing which variant you are facing helps you choose the right approach.

When to Use Interval Techniques

Signs that you are facing an interval problem:

When these techniques might NOT apply:

Example Walkthrough 1: Meeting Rooms I (LeetCode 252)

Let us work through a problem that uses basic overlap detection.

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).

Example Walkthrough 2: Interval List Intersections (LeetCode 986)

This problem demonstrates the two-pointer approach with 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) extra space).

Common Mistakes

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. Using the wrong one gives incorrect results.

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 expect the original array to remain unchanged. Creating a copy before sorting avoids this issue.