Solution: Non-overlapping Intervals

Statement▼

Given an array of intervals where intervals[i] contains the half-open intervalAn interval that contains only one of its boundary elements. The “(” parenthesis denotes the exclusion of the starting point. The “]” bracket denotes the inclusion of the ending point., $(start_{i}, end_{i}]$ , your task is to find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note: Two intervals $(a, b]$ and $(c, d]$ are considered overlapping if there exists a value $x$ such that $a < x \leq b$ and $c < x \leq d$ . In other words, if there is any point within both intervals (excluding their starting points) where both intervals have values, they are considered overlapping. For example, the intervals $(7, 11]$ and $(10, 12]$ are overlapping, whereas the intervals $(2, 4]$ and $(4, 5]$ are non-overlapping.

Constraints:

$1 \leq$ intervals.length $\leq 10^3$
intervals[i].length $== 2$
$−5 \times 10^4 \leq start_{i} < end_{i} \leq 5 \times 10^4$

Here are the steps of the algorithm:

Sort the intervals array in an ascending order based on the end time of each interval.
Declare two variables that will assist us in the algorithm:
- end: This stores the end time of the last included interval.
- remove: This stores the number of intervals to be removed. It is initialized to $0$ .
Traverse the sorted intervals array to determine which interval needs to be excluded. For each interval, the following conditions are checked:
- If the start time of the current interval is greater than or equal to end, this interval does not overlap with the previously included interval and can be included. Therefore, we update end to the end time of the current interval, which is the next earliest possible end time.
- Otherwise, the current interval overlaps with the previously included intervals. Therefore, it must be removed, so we increment remove.
After the sorted intervals array has been traversed completely, there are no more intervals left to evaluate, so we return remove, which now contains the minimum number of intervals to be removed.

The slides below illustrate how the algorithm runs:

Suppose we have the intervals $(4,5], (0,2], (2,7], (1,3],$ and $(0,4]$ passed in as the input. Based on the algorithm discussed above, we would first sort the intervals by their end time and then select the intervals that should be removed. This would lead to the non-overlapping intervals $(0, 2]$ and $(4, 5]$ being selected. Therefore, we would have to remove $3$ intervals.

However, there are other solutions to the above input, giving the same result. Let’s take a look at them:

Intervals included: $(0, 4]$ , $(4, 5]$
Number of intervals excluded: $3$
Intervals included: $(1, 3]$ , $(4, 5]$
Number of intervals excluded: $3$ ...

⋮

Tap here to switch tabs

Problem

Submissions

Solution

Home

Courses

Grokking the Coding Interview Patterns

Solution: Non-overlapping Intervals

Statement▼

Note: Two intervals $(a, b]$ and $(c, d]$ are considered overlapping if there exists a value $x$ such that $a < x \leq b$ and $c < x \leq d$ . In other words, if there is any point within both intervals (excluding their starting points) where both intervals have values, they are considered overlapping. For example, the intervals $(7, 11]$ and $(10, 12]$ are overlapping, whereas the intervals $(2, 4]$ and $(4, 5]$ are non-overlapping.

Constraints:

$1 \leq$ intervals.length $\leq 10^3$
intervals[i].length $== 2$
$−5 \times 10^4 \leq start_{i} < end_{i} \leq 5 \times 10^4$

Here are the steps of the algorithm:

Sort the intervals array in an ascending order based on the end time of each interval.
Declare two variables that will assist us in the algorithm:
- end: This stores the end time of the last included interval.
- remove: This stores the number of intervals to be removed. It is initialized to $0$ .
Traverse the sorted intervals array to determine which interval needs to be excluded. For each interval, the following conditions are checked:
- If the start time of the current interval is greater than or equal to end, this interval does not overlap with the previously included interval and can be included. Therefore, we update end to the end time of the current interval, which is the next earliest possible end time.
- Otherwise, the current interval overlaps with the previously included intervals. Therefore, it must be removed, so we increment remove.
After the sorted intervals array has been traversed completely, there are no more intervals left to evaluate, so we return remove, which now contains the minimum number of intervals to be removed.

The slides below illustrate how the algorithm runs:

However, there are other solutions to the above input, giving the same result. Let’s take a look at them:

Intervals included: $(0, 4]$ , $(4, 5]$
Number of intervals excluded: $3$
Intervals included: $(1, 3]$ , $(4, 5]$
Number of intervals excluded: $3$ ...

Solution: Non-overlapping Intervals

Statement▼

Solution

Why it works

Solution: Non-overlapping Intervals

Statement▼

Solution

Why it works