Minimum Interval Selection to Cover Target Intervals solution and explanation
3 more videos on this problem
Leetcode 4086 | Minimum Interval Selection to Cover Target Intervals | Leetcode weekly contest 524CodeWithMeGuys · 25:07 · 324 views
Minimum Interval Selection to Cover Target Intervals | Sort, Merge and Greedily Pick | Leetcode 4086Manjeet Dhayal · 12:14 · 135 views
LeetCode 4086. Minimum Interval Selection to Cover Target Intervals | Weekly Contest 524 Q4WiniQuest · 32:13 · 111 views
LeetCode 4086 Minimum Interval Selection to Cover Target Intervals — furthest-reach greedy, provedPrateek Goel · 14:24 · 51 views
The problem
You are given two 2D integer arrays, availableIntervals and targetIntervals, each representing a list of closed intervals.
Select a subset of intervals from availableIntervals so that every real point contained in any interval in targetIntervals belongs to at least one selected interval.
Points outside the target intervals do not need to be covered. Selected intervals may overlap or extend beyond the target intervals.
Return the minimum number of intervals you need to select. If it is impossible to cover all the target intervals, return -1.
Example 1:
Input: availableIntervals = [[1,4],[1,7],[3,9],[5,10],[10,15]], targetIntervals = [[1,3],[2,5],[7,8],[10,13],[11,15],[12,13]]
Output: 3
Explanation:
The target intervals cover the ranges [1, 5], [7, 8], and [10, 15]. By selecting [1, 4], [3, 9], and [10, 15] from availableIntervals, all target intervals can be fully covered with three intervals.
Example 2:
Input: availableIntervals = [[4,6],[1,4],[2,5]], targetIntervals = [[3,4],[2,5],[6,7]]
Output: -1
Explanation:
It is impossible to select intervals from availableIntervals to cover all the intervals in targetIntervals.
Example 3:
Input: availableIntervals = [[1,2],[3,4]], targetIntervals = [[1,4]]
Output: -1
Explanation:
Selecting both available intervals leaves every real point strictly between 2 and 3 uncovered. For example, 2.5 belongs to the target interval but to neither available interval.
Constraints:
1 <= availableIntervals.length, targetIntervals.length <= 5 * 104availableIntervals[i].length == targetIntervals[j].length == 21 <= availableIntervals[i][0] <= availableIntervals[i][1] <= 1051 <= targetIntervals[j][0] <= targetIntervals[j][1] <= 105
Approach overview
Problem Overview: You get a list of candidate intervals and a list of target intervals. Select the fewest candidate intervals so that every target interval is fully contained inside at least one selected interval.
Approach 1: Brute Force Subset Search (O(2^n * m) Time, O(n) Space)
Generate every subset of the candidate intervals and check whether each subset covers all targets. For each subset, test every target against the selected intervals. Track the smallest valid subset. This is correct but exponential. It only works as a baseline to confirm your understanding of what "covered" means.
Approach 2: Greedy with Sorting and Sweep (O(n log n + m log m) Time, O(n + m) Space)
Sort the targets by right endpoint and the candidates by left endpoint. Sweep through the targets in order. For each uncovered target, look at every candidate whose left endpoint is at or before the target's left endpoint, and pick the one with the largest right endpoint that still reaches the target. Each pick advances coverage as far as possible, so the greedy choice never hurts. Use a pointer into the sorted candidates so you never rescan. This is the standard greedy interval covering pattern and it is the approach you should aim for.
Approach 3: Sorted Candidates with Heap-Based Selection (O(n log n + m log n) Time, O(n) Space)
Sort candidates by left endpoint and push eligible ones into a max-heap keyed by right endpoint as you advance through targets. When a target needs coverage, pop the heap top to get the candidate that reaches farthest. Discard candidates that cannot reach the current target. This gives the same answer as Approach 2 and makes the "best candidate so far" logic explicit. It is useful when the eligibility test is more complex than a simple endpoint comparison.
Recommended for interviews: Start by describing the brute force so the interviewer sees you understand the coverage condition. Then move to the greedy sweep in Approach 2. The brute force shows understanding, but the greedy proof and the sorting-based sweep show skill. Be ready to explain why picking the reachable candidate with the farthest right endpoint is always safe.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Search | O(2^n * m) | O(n) | Only to verify correctness on tiny inputs |
| Greedy Sort and Sweep | O(n log n + m log m) | O(n + m) | General case and interview answer |
| Heap-Based Selection | O(n log n + m log n) | O(n) | When eligibility rules are more complex than endpoint checks |
Frequently asked questions
Is Minimum Interval Selection to Cover Target Intervals easy or hard?
It is rated Hard, with a 30.8% acceptance rate. The difficulty comes from proving that the greedy choice of the farthest reaching candidate is optimal, not from the code itself, which is short once the sweep is clear.
Minimum Interval Selection to Cover Target Intervals Python or Java solution?
Both are straightforward. In Python, sort with key lambdas and use a simple while loop with a pointer. In Java, sort arrays with Arrays.sort using a comparator, and use PriorityQueue for the heap variant. Focus on the sort-and-sweep logic, since the language syntax is minor.
How to solve Minimum Interval Selection to Cover Target Intervals in O(n log n)?
Sort both lists, then use a pointer over the sorted candidates while iterating through the sorted targets. Keep track of the best right endpoint among candidates that start at or before the current target's left endpoint. When the current target is not yet reached by your chosen interval, select that best candidate and increment the count.
What is the best approach for Minimum Interval Selection to Cover Target Intervals?
The best approach is a greedy sort-and-sweep. Sort targets by right endpoint and candidates by left endpoint, then for each uncovered target pick the reachable candidate with the largest right endpoint. It runs in O(n log n + m log m) time and O(n + m) space.
What data structure is used in Minimum Interval Selection to Cover Target Intervals?
The greedy solution uses sorted arrays and a pointer. The heap-based variant uses a max-heap keyed by right endpoint to pick the candidate that reaches farthest. No complex tree structures are required.
What is the time complexity of Minimum Interval Selection to Cover Target Intervals?
The optimal greedy solution runs in O(n log n + m log m) time, dominated by sorting the candidate and target intervals. The brute force subset search is O(2^n * m) and is only practical for very small inputs.
Is Minimum Interval Selection to Cover Target Intervals asked at Google, Amazon, or Meta?
This problem is tagged as General on FleetCode, so no specific company frequency is confirmed. Interval covering and greedy sweep patterns appear often in interviews at large tech companies, so the technique is worth mastering regardless.