Non-overlapping Intervals Greedy DSA Solution - Study Chapter | QuizMaker

Non-overlapping Intervals explained with subset brute force, optimized earliest-end greedy, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 13: Greedy Algorithms

Learning Outcome

After this lesson, you should be able to sort by ending time and keep the maximum number of compatible intervals.

Problem Statement

Given intervals, return the minimum number of intervals to remove so the rest do not overlap.

Input	Output	Why
`intervals = [[1,2],[2,3],[3,4],[1,3]]`	`1`	Removing [1,3] leaves [1,2], [2,3], and [3,4], which do not overlap.

Brute Force Approach

Try every subset of intervals and choose the largest non-overlapping subset. This is exponential.

Optimized Approach

Sort intervals by end time. Keep an interval when its start is at or after the last kept end.

Exact Pseudocode

sort intervals by end
kept = 0
lastEnd = -infinity
for interval in intervals:
  if interval.start >= lastEnd:
    kept += 1
    lastEnd = interval.end
return intervals.length - kept

Reference Code

class Solution:
    def eraseOverlapIntervals(self, intervals):
        intervals.sort(key=lambda x: x[1])
        kept = 0
        last_end = float("-inf")

        for start, end in intervals:
            if start >= last_end:
                kept += 1
                last_end = end

        return len(intervals) - kept

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });

        int kept = 0;
        long long lastEnd = LLONG_MIN;
        for (auto& interval : intervals) {
            if (interval[0] >= lastEnd) {
                kept++;
                lastEnd = interval[1];
            }
        }

        return intervals.size() - kept;
    }
};

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int kept = 0;
        long lastEnd = Long.MIN_VALUE;
        for (int[] interval : intervals) {
            if (interval[0] >= lastEnd) {
                kept++;
                lastEnd = interval[1];
            }
        }

        return intervals.length - kept;
    }
}

Sample Dry Run

Step	State	Result
Sort by end	[1,2], [2,3], [1,3], [3,4]	Earliest finish first
Keep [1,2]	lastEnd = 2	kept = 1
Keep [2,3]	2 >= 2	kept = 2
Skip [1,3]	1 < 3	remove one interval

Complexity

Measure	Value	Reason
Time	O(n log n)	Sorting dominates the runtime.
Space	O(1)	Only counters and the last kept end are stored.

Edge Cases

Touching intervals like [1,2] and [2,3] do not overlap.
An empty list needs 0 removals.
Sort by end time, not by interval length.

Interview Checklist

Keep the interval that ends earliest.
Count kept intervals, then subtract from total.
Use start >= lastEnd for non-overlap.

FAQs

Why sort by end?

The earliest ending interval leaves the most room for future intervals.

Why count kept intervals?

Min removals equals total intervals minus the maximum number that can be kept.

What is the core pattern?

Earliest-end interval greedy.