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.

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.

Description Hints 7 Video 25:07

4086. Minimum Interval Selection to Cover Target Intervals

Q: 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.

Hard30.8% acceptance

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 * 10⁴
availableIntervals[i].length == targetIntervals[j].length == 2
1 <= availableIntervals[i][0] <= availableIntervals[i][1] <= 10⁵
1 <= targetIntervals[j][0] <= targetIntervals[j][1] <= 10⁵

Hints open one at a time

Hint 1

1a (Sorting and Greedy): Sort both lists by left endpoint and merge overlapping target intervals. Intervals sharing an endpoint can be merged, but intervals separated by a positive gap cannot.

Hint 2

1b (Sorting and Greedy): At the start of an uncovered target interval, choose an available interval containing that point whose right endpoint is farthest.

Hint 3

1c (Sorting and Greedy): If coverage currently reaches x inside a target interval, the next selected interval must start at or before x and extend beyond it. Do not advance to x + 1, since every real point must be covered.

Hint 4

1d (Sorting and Greedy): Once a target interval is covered, move to the next target interval while retaining the coverage already obtained. Return -1 if a required point cannot be covered or coverage cannot be extended.

Hint 5

2a (Doubled-Coordinate Sweep): Map each interval [l, r] to the integer positions from 2 * l through 2 * r. These positions represent original integer coordinates and their midpoints, which suffice because all interval endpoints are integers.

Hint 6

2b (Doubled-Coordinate Sweep): Use a difference array to mark required positions. For each position, precompute the farthest right endpoint among available intervals starting at or before it.

Hint 7

2c (Doubled-Coordinate Sweep): Sweep from left to right. Whenever a required position is not covered, select the interval reaching farthest right that covers it. If none exists, return -1.

LanguageLoading editor…

1class Solution:
2    def minSelection(self, availableIntervals: List[List[int]], targetIntervals: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[1,4],[1,7],[3,9],[5,10],[10,15]]
[[1,3],[2,5],[7,8],[10,13],[11,15],[12,13]]

Input

[[4,6],[1,4],[2,5]]
[[3,4],[2,5],[6,7]]

Input

[[1,2],[3,4]]
[[1,4]]

Your code is saved on this device.