Non-overlapping Intervals
Non-overlapping Intervals is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Interval Merging/Scheduling subpattern.
- Blind 75 · #65 of 75 · Intervals
- NeetCode 150 · #132 of 150 · Intervals
- NeetCode 250 · #223 of 250 · Intervals
Problem statement
You are given intervals, where each element is an interval represented by two integers [start, end]. An interval covers the positions from start through end; two intervals overlap when they share any interior portion. Intervals that meet exactly at an endpoint do not overlap.
Remove as few intervals as possible so that every pair of remaining intervals is non-overlapping. Return the minimum number of intervals that must be removed.
Example 1:
Input: intervals = [[1,3],[3,6],[6,10]] Output: 0 Explanation: Each interval only touches the next one at an endpoint, so none of them overlap.
Example 2:
Input: intervals = [[1,4],[2,3],[5,7],[6,8]] Output: 2 Explanation: One interval must be removed from each overlapping pair of groups; for instance, keep [2,3] and [5,7].
Example 3:
Input: intervals = [[1,10],[2,4],[3,7],[8,9]] Output: 2 Explanation: The interval [1,10] overlaps all three shorter intervals, and [2,4] overlaps [3,7]. Removing [1,10] and either one of [2,4] or [3,7] leaves a non-overlapping set.
Constraints:
- 1 <= intervals.length <= 10^5 - Each element of intervals contains exactly 2 integers. - For every interval [start, end], start < end. - 1 <= start <= 5 10^4. - 1 <= end <= 5 10^4.
Topics and companies
Topics: Array, Greedy, Sorting.
How to practise Non-overlapping Intervals on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n), due to sorting the intervals. time and O(log n) auxiliary space for the sorting recursion stack, excluding the input array. space.
Open Non-overlapping Intervals in the code editor, or read the Non-overlapping Intervals editorial for a worked solution with its approach and complexity analysis.
Where Non-overlapping Intervals sits in the DSA pattern sheet
- Greedy Patterns pattern guide
- Interval Merging/Scheduling subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Non-overlapping Intervals
Other problems that use the same Interval Merging/Scheduling and Greedy Patterns techniques:
- Divide Intervals Into Minimum Number of Groups — Medium, same subpattern
- Insert Interval — Medium, same subpattern
- Meeting Rooms — Easy, same subpattern
- Merge Intervals — Medium, same subpattern
- Assign Cookies — Easy, same pattern
- Candy — Hard, same pattern