Remove Covered Intervals

LeetCode 1222 | Difficulty: Medium

Medium

Problem Description

Given an array intervals where intervals[i] = [l~i~, r~i~] represent the interval [l~i~, r~i~), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

Input: intervals = [[1,4],[2,3]]
Output: 1

Constraints:

• 1 <= intervals.length <= 1000

• intervals[i].length == 2

• 0 <= l~i~ < r~i~ <= 10^5

• All the given intervals are unique.

Topics: Array, Sorting

---

Approach

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 145 ms)

Metric	Value
Runtime	145 ms
Memory	40.1 MB
Date	2022-02-20

Solution

public class Solution {
    public int RemoveCoveredIntervals(int[][] intervals) {
        Array.Sort(intervals, Comparer<int[]>.Create((x,y) => x[0] == y[0] ? y[1]-x[1] : x[0]-y[0]));
	int right = 0, result = 0;
	foreach (var interval in intervals)
	{
		int x = interval[0];
		int y = interval[1];
		if(y>right)
		{
			result++;
			right = y;
		}
	}
	return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: How to check if an interval is covered by another?

Hint 2: Compare each interval to all others and check if it is covered by any interval.