Remove Covered Intervals

Medium
348.

Remove Covered Intervals

Remove Covered Intervals is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

Given an array of intervals where intervals[i] = [l, r], remove every interval that is covered by another one, then return the number of intervals left.

Interval [a, b) is covered by [c, d) when c <= a and b <= d.

Example 1

Input
intervals = [[1,4],[3,6],[2,8]]
Output
2
Explanation
[3,6] is covered by [2,8].

Example 2

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

Example 3

Input
intervals = [[0,10],[5,12]]
Output
2

Constraints

  • 1 <= intervals.length <= 30
  • 0 <= l < r <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var removeCoveredIntervals = function(intervals) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Covered Intervals — Solution in Python, Java & C++

Remove Covered Intervals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Remove Covered Intervals is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of intervals where intervals[i] = [l, r], remove every interval that is covered by another one, then return the number of intervals left.

Interval [a, b) is covered by [c, d) when c <= a and b <= d.

Example 1

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

Example 2

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

Example 3

Input: intervals = [[0,10],[5,12]]
Output: 2

Constraints

  • 1 <= intervals.length <= 30
  • 0 <= l < r <= 1000

Hints for Remove Covered Intervals

  1. Hint 1

    Sort by left endpoint ascending; ties must break by right endpoint descending.

  2. Hint 2

    That tie-break puts a covering interval before the ones it swallows.

  3. Hint 3

    Then keep an interval only when its right endpoint exceeds the largest right endpoint seen so far.

How to solve Remove Covered Intervals

Sort by left ascending, ties by right descending; then an interval survives only if its right endpoint exceeds the largest right endpoint seen so far.

Approach

  1. Sort by (l, -r).
  2. Walk with right = -1; when r > right, count it and set right = r.

Why it works

After sorting, every earlier interval starts at or before the current one, so the current interval is covered exactly when some earlier interval also reaches at least as far right. The tie-break puts the covering interval first when lefts are equal.

Complexity

  • Time — O(n log n)
  • Space — O(1) beyond the sort

Pitfalls

  • Ties by right ascending would count the covered interval before its cover.

Reference solution

Python

def removeCoveredIntervals(intervals) -> int:
    ordered = sorted(intervals, key=lambda p: (p[0], -p[1]))
    count = 0
    right = -1
    for l, r in ordered:
        if r > right:
            count += 1
            right = r
    return count

Java

public static int removeCoveredIntervals(int[][] intervals) {
    int[][] s = intervals.clone();
    Arrays.sort(s, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
    int count = 0, right = -1;
    for (int[] iv : s) {
        if (iv[1] > right) {
            count++;
            right = iv[1];
        }
    }
    return count;
}

C++

int removeCoveredIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> s = intervals;
    sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] > b[1];
    });
    int count = 0, right = -1;
    for (const auto& iv : s) {
        if (iv[1] > right) {
            count++;
            right = iv[1];
        }
    }
    return count;
}

JavaScript

var removeCoveredIntervals = function(intervals) {
    const sorted = intervals.slice().sort(function(a, b) {
        return a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1];
    });
    let count = 0, right = -1;
    for (let i = 0; i < sorted.length; i++) {
        if (sorted[i][1] > right) {
            count++;
            right = sorted[i][1];
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms