Maximum Non-Overlapping Intervals Count
Maintained by Vikas D, software engineer
You are handed a set of intervals, each written as a pair [start, end] that covers every point from start through end, endpoints included. Two intervals are considered to clash whenever their ranges meet at all, even if they only share a single endpoint. Concretely, [a, b] and [c, d] clash when a <= d and c <= b.
Your goal is to keep as large a subset as you can in which every pair of kept intervals is mutually clash free, then report how many intervals that subset holds. You do not return the intervals themselves, only the count.
Because the touch case counts as a clash, an interval ending at 5 cannot sit beside one starting at 5; the next interval has to start strictly after the previous one ends. This is the classic activity-selection setup, framed so that shared boundaries are not allowed.
Think of each interval as a meeting that occupies a room for its whole span. You want to book the most meetings into one room without any two of them brushing against each other in time.
Examples
Pick [1,2] first. [2,3] starts at 2, which is not strictly after 2, so it clashes and is skipped. [3,4] starts at 3, strictly after 2, so it is kept. That gives 2, and no selection does better because any third interval would touch one already chosen.
All three occupy the exact same span, so at most one can be kept. The other two clash with whichever you pick.
The wide [1,10] swallows the other three, so keeping it limits you to one interval. Drop it instead and keep [2,3], [4,5], [6,7]; each starts strictly after the previous ends, giving 3.
Constraints
- 1 <= intervals.length <= 10^5
- Every interval has exactly two values, start and end
- -5 * 10^4 <= start < end <= 5 * 10^4, so each interval is non-empty
- Intervals are closed: sharing a single endpoint still counts as a clash
Visible test cases
- maxNonOverlapping([[1,2],[2,3],[3,4],[1,3]]) == 2
- maxNonOverlapping([[1,2],[1,2],[1,2]]) == 1
- maxNonOverlapping([[1,3],[2,4],[3,5]]) == 1
- maxNonOverlapping([[1,2],[3,4],[5,6]]) == 3
- maxNonOverlapping([[1,10],[2,3],[4,5],[6,7]]) == 3
Hints
Hint 1
When you are forced to choose between two intervals that clash, which one leaves the most room for future picks? The one that frees up the timeline soonest.
Hint 2
Sort the intervals by their end value. Then sweep left to right, keeping an interval only when its start sits strictly beyond the end of the last one you kept.
Hint 3
Track a single number, the end of the most recently kept interval. An incoming interval qualifies only if its start is strictly greater than that number, because equal endpoints clash here.
Approaches
Brute force over subsets
Time O(2^n * n^2) · Space O(n)Try every possible subset of intervals, discard any subset that contains a clashing pair, and remember the size of the largest clash-free subset. Correct but hopeless at scale.
- Enumerate all 2^n subsets of the interval list.
- For each subset, check every pair to confirm no two intervals satisfy a <= d and c <= b.
- If the subset is fully clash free, compare its size against the best seen so far.
- Return the largest valid size found.
Greedy by earliest end
Time O(n log n) · Space O(n)Among intervals competing for the same stretch of time, the one that ends earliest blocks the least of the future, so always commit to the available interval with the smallest end. Sorting by end lets a single left-to-right sweep make that choice every step.
- Sort the intervals in increasing order of their end value.
- Initialise a counter at 0 and a marker lastEnd at negative infinity.
- Walk through the sorted intervals; for each one, keep it only when its start is strictly greater than lastEnd.
- When you keep an interval, increment the counter and set lastEnd to that interval's end.
- Return the counter after the sweep.
Common mistakes
- Allowing intervals that merely touch. Since endpoints are inclusive here, an interval starting at the previous end clashes, so the keep test must be start > lastEnd, not start >= lastEnd.
- Sorting by start instead of by end. Sorting by start can force you to commit to a long interval early and miss several short ones that would have fit.
- Returning the number of intervals you had to drop instead of the number you kept. This problem asks for the kept count, which is the related but opposite figure.
- Initialising lastEnd to 0 rather than negative infinity. Because starts can be negative, a 0 seed would wrongly reject valid early intervals.
- Mutating the caller's array with an in-place sort when the surrounding code still needs the original order. Sort a copy if that matters.
Follow-up variations
- How would the answer change if intervals were half-open, so [a, b) and [b, c) do not clash? The keep test loosens to start >= lastEnd.
- Instead of the maximum count kept, return the minimum number of intervals to remove so the rest are clash free. It is the total count minus the answer here.
- What if each interval carried a weight and you wanted the maximum total weight of a clash-free subset rather than the maximum count? Greedy breaks; this needs sorting plus dynamic programming with binary search.
- How would you also report one actual selection that achieves the maximum, not just its size?