Solving Non-overlapping Intervals with Greedy Approach

1. Introduction and Core Concepts

Non-overlapping intervals is one of the most fundamental problems in the family of greedy algorithms and interval scheduling. Given a collection of intervals, each defined by a start time and an end time, the goal is to find the maximum subset of intervals that do not overlap with each other, or equivalently, to determine the minimum number of intervals that must be removed to make the remaining intervals non-overlapping. This deceptively simple problem appears in countless real-world scenarios and serves as a gateway to understanding greedy choice properties and optimal substructure.

Formally, an interval can be represented as [start, end) or [start, end] depending on whether touching endpoints are considered overlapping. In the classic LeetCode 435 formulation (Non-overlapping Intervals), intervals that only touch at the endpoint, such as [1,2] and [2,3], are considered non-overlapping. Two intervals [s1, e1] and [s2, e2] overlap if s1 < e2 and s2 < e1. The problem asks us to maximize the number of compatible intervals we can keep.

Why does this problem matter? Beyond its frequency in coding interviews at top technology companies, it teaches a critical lesson: not all optimization problems require dynamic programming or exhaustive search. When a problem exhibits the greedy-choice property — where a locally optimal choice leads to a globally optimal solution — a simple sorting step followed by a single linear scan can yield an optimal answer with remarkable efficiency. Mastering non-overlapping intervals builds intuition for more complex scheduling, resource allocation, and packing problems that power operating systems, cloud infrastructure, and logistics.

Key Definitions

To reason correctly about this problem, we must define a few core terms. An interval set is a collection of n intervals intervals = [[s0, e0], [s1, e1], ..., [sn-1, en-1]]. A feasible solution is any subset where no two intervals overlap. The objective is to maximize the size of this feasible subset. The complement of this objective is minimizing removals, where minRemovals = n - maxNonOverlappingCount. Understanding this duality is essential because many problem statements phrase the question in terms of removals while the algorithm naturally computes the maximum keepable set.

Another important concept is the difference between interval partitioning and interval scheduling. Interval scheduling, which is what non-overlapping intervals solves, seeks to maximize the number of intervals scheduled on a single resource. Interval partitioning, by contrast, seeks to minimize the number of resources needed to schedule all intervals. While related, they require different greedy strategies, and confusing them is a common source of errors for beginners.

2. How It Works

The greedy approach to non-overlapping intervals is elegant and relies on a single, powerful insight: the interval that finishes earliest leaves the most room for the remaining intervals. Therefore, to maximize the number of intervals we can keep, we should always prefer the interval with the smallest end time among the remaining compatible intervals. This is known as the Earliest Finishing Time (EFT) strategy.

The algorithm proceeds in two phases. First, sort all intervals by their end time in ascending order. If two intervals have the same end time, sorting by start time secondarily can be helpful but is not strictly required for correctness. Second, iterate through the sorted intervals, maintaining the end time of the last interval that was selected. For each interval in sorted order, if its start time is greater than or equal to the end time of the last selected interval, it is compatible and we select it, updating the last end time. Otherwise, it overlaps and must be skipped or counted as a removal.

Why does sorting by end time work while sorting by start time or by duration fails? Consider intervals [1,10], [2,3], [4,5]. Sorting by start time would pick [1,10] first, blocking the other two and yielding a solution of size 1. Sorting by shortest duration would also be suboptimal in other cases. Sorting by end time correctly picks [2,3] then [4,5], yielding the optimal size of 2. The earliest finishing interval is the least constraining choice, which is the hallmark of a correct greedy choice.

Proof of Optimality: The Exchange Argument

The correctness of this greedy algorithm can be proven using an exchange argument. Let G be the set produced by the greedy algorithm and O be an optimal solution. Both are sorted by end time. We can show by induction that for every k, the k-th interval in G finishes no later than the k-th interval in O. This means G never falls behind O in terms of resource availability.

If O and G differ, let j be the first index where they differ. We can replace the j-th interval in O with the j-th interval in G without creating any overlap, because G[j] finishes earlier. Repeating this exchange transforms O into G without reducing its size, proving that G is also optimal. This proof technique is broadly applicable to many greedy scheduling problems and is worth studying deeply.

This greedy property only holds for the unweighted version of the problem, where every interval has equal value. If intervals have weights or profits and the goal is to maximize total weight, the greedy choice fails and dynamic programming with binary search is required, which is known as Weighted Interval Scheduling.

3. Implementation

Implementing the greedy solution in Python is concise, but attention to edge cases and sorting stability is important. The core logic requires only a sort and a single pass, making it easy to implement correctly under interview pressure once the pattern is understood.

Basic Solution: Minimum Removals

This is the most common interview formulation, where you must return the minimum number of intervals to remove. The function sorts by end time and counts overlaps.

def eraseOverlapIntervals(intervals):
    """
    Return minimum number of intervals to remove to make
    the rest non-overlapping.
    Greedy: Sort by end time, keep earliest finishing intervals.
    """
    if not intervals:
        return 0

    # Sort by end time to prioritize earliest finishing interval
    intervals.sort(key=lambda x: x[1])

    removals = 0
    prev_end = intervals[0][1]
    # We keep the first interval after sorting
    count_kept = 1

    for i in range(1, len(intervals)):
        start, end = intervals[i]
        # If current interval overlaps with last kept interval
        if start < prev_end:
            # Overlap: must remove current interval
            removals += 1
        else:
            # No overlap: keep it and update prev_end
            count_kept += 1
            prev_end = end

    return removals

# Example usage
intervals = [[1,2],[2,3],[3,4],[1,3]]
print(eraseOverlapIntervals(intervals))  # Output: 1

Variant: Return the Actual Non-Overlapping Set

In many practical applications, we need not just the count but the actual intervals to keep. This variant builds and returns the selected subset, which is useful for scheduling and resource allocation.

def getNonOverlappingIntervals(intervals):
    """
    Return the maximum set of non-overlapping intervals.
    """
    if not intervals:
        return []

    # Sort by end time, then by start time for determinism
    intervals.sort(key=lambda x: (x[1], x[0]))

    selected = [intervals[0]]
    prev_end = intervals[0][1]

    for start, end in intervals[1:]:
        # Compatible if start is >= prev_end (touching is allowed)
        if start >= prev_end:
            selected.append([start, end])
            prev_end = end
        # else: skip overlapping interval

    return selected

# Example
intervals = [[1,4],[2,3],[3,5],[4,6]]
print(getNonOverlappingIntervals(intervals))
# Output: [[2,3], [3,5]] or [[2,3],[4,6]] depending on tie-breaking

Counting Maximum Non-Overlapping Intervals

This formulation directly computes the maximum number of meetings that can be held in a single room, which is the dual of the removal problem.

def maxNonOverlapping(intervals):
    """
    Return maximum number of non-overlapping intervals
    that can be selected.
    """
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])

    count = 0
    prev_end = float('-inf')

    for start, end in intervals:
        if start >= prev_end:
            count += 1
            prev_end = end

    return count

# Equivalent to n - eraseOverlapIntervals(intervals)
intervals = [[0,30],[5,10],[15,20]]
print(maxNonOverlapping(intervals))  # Output: 2

Robust Implementation with Input Validation

A production-ready implementation should handle edge cases such as empty input, single intervals, intervals with equal endpoints, and invalid intervals where start is greater than end.

def eraseOverlapIntervalsRobust(intervals):
    """
    Robust version with validation and handling of edge cases.
    """
    if not intervals or len(intervals) <= 1:
        return 0

    # Validate intervals
    valid_intervals = []
    for s, e in intervals:
        if s > e:
            raise ValueError(f"Invalid interval [{s}, {e}]: start > end")
        valid_intervals.append([s, e])

    valid_intervals.sort(key=lambda x: x[1])

    removals = 0
    prev_end = valid_intervals[0][1]

    for start, end in valid_intervals[1:]:
        if start < prev_end:
            removals += 1
            # Note: we do NOT update prev_end when we remove
            # We keep the earlier finishing interval
        else:
            prev_end = end

    return removals

# Edge cases
print(eraseOverlapIntervalsRobust([]))  # 0
print(eraseOverlapIntervalsRobust([[1,2]]))  # 0
print(eraseOverlapIntervalsRobust([[1,2],[1,2],[1,2]]))  # 2

4. Step-by-Step Example

Let us walk through a concrete example to see exactly how the greedy choice unfolds. Consider the interval set intervals = [[1,2], [2,3], [3,4], [1,3]]. The goal is to find the minimum removals needed.

Step 1: Sort by end time. The unsorted list is [[1,2], [2,3], [3,4], [1,3]]. Sorting by the second element (end time) yields [[1,2], [1,3], [2,3], [3,4]]. Note that [1,3] and [2,3] both end at 3; their relative order does not affect the final count, but sorting stably helps with tracing.

Step 2: Initialize. We select the first interval [1,2] as our initial kept interval. We set prev_end = 2, kept = [[1,2]], and removals = 0. This is our baseline; the earliest finishing interval is always part of some optimal solution.

Step 3: Iterate. Next interval is [1,3]. Its start 1 < prev_end (2), so it overlaps with [1,2]. We must remove it. removals = 1, prev_end stays at 2. We keep the interval that ends earlier because it leaves more room.

Step 4: Next interval is [2,3]. Its start 2 >= prev_end (2), so it does not overlap (touching is allowed). We keep it. Now kept = [[1,2], [2,3]] and prev_end = 3.

Step 5: Next interval is [3,4]. Its start 3 >= prev_end (3), so it is also compatible. We keep it. Final kept set is [[1,2], [2,3], [3,4]] with prev_end = 4 and removals = 1. The algorithm terminates and returns 1, which is optimal.

Visual Trace Table

The following table shows the decision at each step, which is a useful way to trace the algorithm during an interview or debugging session.

Consider a second, more challenging example: [[1,100], [11,22], [1,11], [2,12]]. After sorting by end time we get [[1,11], [2,12], [11,22], [1,100]]. The greedy algorithm picks [1,11], then [11,22], skipping the other two, for a total of 2 kept and 2 removed. Any solution that picks [1,100] first can keep only one interval, proving again why earliest finish time dominates.

5. Complexity Analysis

Understanding the time and space complexity of the greedy solution is crucial for evaluating its scalability and for comparing it against alternative approaches like brute force or dynamic programming.

The dominant operation is sorting. Sorting n intervals by end time takes O(n log n) time using Python's Timsort, which is a hybrid of merge sort and insertion sort. The subsequent linear scan is O(n) time, as each interval is examined exactly once with constant-time comparison and update operations. Therefore, the overall time complexity is O(n log n) in all cases — best, average, and worst — because sorting dominates and Python's sort is O(n log n) regardless of initial order, except for already sorted inputs where it can approach O(n) due to adaptive behavior.

Space complexity is O(1) auxiliary space if we sort in-place and only count removals, or O(n) if we need to return the actual selected intervals. If we are not allowed to modify the input, we must copy the array before sorting, which costs O(n) extra space. Python's sort itself uses O(n) worst-case auxiliary space for Timsort, though this is often considered implementation-dependent and sometimes reported as O(log n) for the recursion stack in other languages.

It is important to distinguish between the complexity of the algorithm and the complexity of the problem. The non-overlapping intervals problem has a lower bound of Omega(n log n) in the comparison model because it can be reduced from sorting, meaning no comparison-based algorithm can do better asymptotically. Thus, the greedy solution is asymptotically optimal.

For very large n (millions of intervals), the O(n log n) sort may become a bottleneck. In streaming or online settings where intervals arrive over time, alternative data structures like balanced binary search trees can maintain the sorted order incrementally, but the offline greedy algorithm remains the most efficient for batch processing.

6. Variations and Optimizations

The classic non-overlapping intervals problem has several important variations that appear in interviews and production systems. Recognizing which variant you are facing is key to choosing the right algorithm.

The first major variation is Weighted Interval Scheduling, where each interval has a profit or weight and the goal is to maximize total profit, not just count. The greedy earliest-finish-time strategy fails here. For example, intervals [1,2] profit 10 and [2,3] profit 10 versus [1,3] profit 100 — greedy would pick the two small intervals for profit 20, missing the optimal single interval with profit 100. This variant requires dynamic programming after sorting by end time, combined with binary search to find the latest non-conflicting interval, achieving O(n log n) time.

A second variation is finding the minimum number of meeting rooms or platforms required to schedule all intervals without overlap. This is the Interval Partitioning problem. The greedy strategy here is different: sort by start time and use a min-heap to track end times of rooms currently in use. If the earliest finishing room is free before the next meeting starts, reuse it; otherwise allocate a new room. This also runs in O(n log n) but uses a heap instead of a simple scan.

A third variation involves intervals that are closed on both ends where touching counts as overlapping. In that case the compatibility condition changes from start >= prev_end to start > prev_end. This subtle off-by-one difference is a frequent source of bugs. Always clarify with the interviewer or problem statement whether [1,2] and [2,3] overlap.

Optimization Techniques

While the basic greedy algorithm is already optimal, there are micro-optimizations and alternative implementations worth knowing. For instance, if intervals are already sorted by end time, the algorithm becomes O(n). In some systems, intervals are inserted in sorted order using a balanced BST, allowing incremental scheduling without re-sorting.

Another optimization is to avoid sorting the original objects when intervals are large or contain payload data. Instead, sort indices or use a key function that extracts only the end time, reducing memory movement. In Python, using intervals.sort(key=lambda x: x[1]) is highly optimized in C and is faster than a custom comparator.

For parallel processing of massive datasets, the intervals can be partitioned by time ranges, solved locally, and then merged. However, this requires careful handling of boundary intervals that cross partitions and is only beneficial when n is extremely large and distributed computing is available.

7. Real-World Applications

The non-overlapping intervals algorithm is far more than an academic exercise; it underpins critical resource allocation decisions in technology and beyond. Its ability to maximize throughput on a single resource with minimal computation makes it ideal for high-frequency scheduling.

In operating systems, CPU scheduling for non-preemptive tasks uses this logic. When a single core must execute the maximum number of jobs without overlapping, each job's start and end time defines an interval, and the greedy scheduler picks the job that frees the CPU earliest. Similarly, in cloud computing, a single virtual machine or container can be allocated to the maximum number of non-overlapping customer requests, maximizing utilization and revenue.

In networking, bandwidth allocation on a single channel follows the same pattern. Packet transmissions, satellite communication windows, and wireless spectrum slots are intervals; selecting the maximum non-overlapping set maximizes channel usage without collisions. Database systems use interval scheduling for lock management and transaction serialization, ensuring that transactions that access overlapping data ranges are not executed concurrently if they conflict.

Beyond computing, the applications are equally compelling. In airline and railway operations, gate or platform assignment for a single gate is an interval scheduling problem. In genomics, selecting the maximum set of non-overlapping genetic markers or exons along a chromosome uses the same algorithm. Even in everyday life, a person trying to attend the maximum number of meetings or classes in a single day is solving non-overlapping intervals intuitively.

The unifying theme across all these domains is the presence of a single, reusable, exclusive resource and a set of requests that require exclusive access for a contiguous time period. Whenever that pattern appears, the greedy earliest-finish-time algorithm is the first tool to consider.

8. Comparison with Alternatives

While the greedy approach is optimal for the unweighted non-overlapping intervals problem, it is instructive to compare it with other algorithmic paradigms to understand when each is appropriate. Choosing the wrong paradigm can lead to exponential time or suboptimal results.

Brute force enumeration tries all subsets of intervals, checking each for overlaps and keeping the largest feasible subset. With n intervals there are 2^n subsets, leading to O(2^n * n) time, which is infeasible for n > 30. Dynamic programming can solve the weighted variant in O(n log n) after sorting, but is overkill for the unweighted case and requires more complex implementation with binary search and memoization. Backtracking with pruning is similar to brute force but can be slightly faster in practice, though still exponential in the worst case.

Another alternative is to model the problem as a graph where each interval is a node and edges connect overlapping intervals. The problem then becomes finding the maximum independent set in an interval graph. While maximum independent set is NP-hard for general graphs, it is polynomial for interval graphs, and the greedy algorithm is essentially the specialized efficient solution for this graph class. Using a general graph algorithm would be unnecessarily complex.

The key takeaway is that greedy is the right choice when all intervals have equal value and you need maximum cardinality. If intervals have different values, you must upgrade to dynamic programming. If you need to schedule all intervals using the minimum number of resources, you need the heap-based interval partitioning algorithm, not the simple greedy scan.

9. Common Mistakes and Best Practices

Despite its simplicity, the non-overlapping intervals problem is a common source of bugs in interviews and production code. Awareness of these pitfalls can save significant debugging time.

The most frequent mistake is sorting by the wrong key. Sorting by start time or by interval duration seems intuitive but leads to suboptimal solutions. For example, sorting by start time fails on [[1,10],[2,3],[4,5]] as discussed earlier. Always sort by end time. A related mistake is forgetting to sort at all and assuming the input is already sorted; unless the problem explicitly guarantees sorted input, you must sort.

The second major pitfall is the overlap condition. Confusing < with <= or > with >= changes whether touching intervals are considered overlapping. In the standard definition, [1,2] and [2,3] do not overlap, so the check is start < prev_end for overlap, or start >= prev_end for compatibility. If the problem defines intervals as inclusive on both ends, the condition becomes start <= prev_end for overlap. Always clarify this with examples.

A third mistake is incorrectly updating prev_end. When an interval is removed due to overlap, prev_end should not be updated; you keep the earlier finishing interval. Some incorrect implementations update prev_end to the current interval's end even when it overlaps, which can cause the algorithm to incorrectly discard future compatible intervals. The update should only happen when you keep an interval.

Best Practices

To avoid these errors, follow a disciplined approach. First, write the sort key explicitly and add a comment explaining why end time is chosen. Second, define a helper function isOverlapping(a, b) to encapsulate the overlap logic and make the boundary condition explicit and testable. Third, handle edge cases at the top of the function: empty list, single interval, and invalid intervals.

Testing is equally important. Create a small test suite that covers: empty input, single interval, all intervals overlapping, no intervals overlapping, intervals that touch at endpoints, intervals with identical end times, and negative time values. Running these tests immediately after implementation catches most logic errors before they reach code review.

Finally, consider immutability. If the caller expects the original interval list to remain unchanged, sort a copy using sorted(intervals, key=lambda x: x[1]) instead of intervals.sort(). This prevents subtle side effects in larger systems where the same interval list is used elsewhere.

10. Interview Questions

Non-overlapping intervals and its variants are staples of technical interviews. Interviewers use them to assess understanding of greedy algorithms, sorting, edge cases, and the ability to adapt a known solution to a new constraint. Below are common questions you should be prepared to answer, along with the key ideas for each.

Q1: Minimum Removals vs. Maximum Non-Overlapping — Are They the Same?

Question: Given intervals, you are asked to return the minimum number to remove. Can you just compute the maximum non-overlapping set and subtract from n? Why does this work? Answer: Yes, because any feasible set of non-overlapping intervals corresponds to a set of intervals to keep, and the complement is the set to remove. Since total = kept + removed and total is fixed, minimizing removals is equivalent to maximizing kept. The greedy algorithm naturally computes the maximum kept, so answer = n - maxKept. Be ready to explain this duality and to implement either version.

Q2: What If Intervals Have Weights or Profits?

Question: Each interval now has a value, and you want to maximize total value, not count. Does the greedy earliest-finish-time still work? If not, how would you solve it? Answer: No, greedy fails for weighted intervals. Provide a counterexample like [1,2] value 1, [2,3] value 1, [1,3] value 100. The correct solution is Weighted Interval Scheduling using dynamic programming: sort by end time, define p[i] as the latest interval before i that does not overlap, and use recurrence dp[i] = max(dp[i-1], value[i] + dp[p[i]]). This requires O(n log n) time with binary search for p[i].

Q3: How Would You Find the Minimum Number of Rooms to Schedule All Meetings?

Question: Instead of maximizing meetings in one room, you must schedule all meetings using the fewest rooms. How does the algorithm change? Answer: This is interval partitioning, not interval scheduling. The greedy strategy changes to sorting by start time and using a min-heap of end times. Iterate intervals sorted by start; if the earliest ending room is free (heap[0] <= current.start), reuse that room (pop and push new end), otherwise allocate a new room (push). The heap size at the end is the answer. Time is O(n log n) and space is O(n).

Q4: How Do You Handle Inclusive Intervals Where Touching Counts as Overlap?

Question: If [1,2] and [2,3] are considered overlapping, how does your code change? Answer: Only the comparison operator changes. Instead of start < prev_end for overlap, use start <= prev_end. Equivalently, compatibility becomes start > prev_end instead of start >= prev_end. This is a one-character change but completely alters the result, so always clarify the interval definition. Test with [[1,2],[2,3]] — answer should be 1 removal if inclusive, 0 if exclusive.

Q5: Can You Solve It Without Sorting? What Is the Lower Bound?

Question: Is O(n log n) the best possible, or can we do O(n)? Answer: In the general comparison model, Omega(n log n) is the lower bound because sorting is reducible to this problem. If intervals are already sorted by end time, the scan is O(n). If end times are bounded integers (e.g., 0 to 1000), you could use counting sort to achieve O(n + k) where k is the range, which is effectively O(n) for small k. Otherwise, comparison-based sorting is required and O(n log n) is optimal.

Mastering these questions and the underlying greedy principle will not only help you solve non-overlapping intervals but also equip you to tackle the broader family of scheduling and resource allocation problems that are central to algorithm design.