Remove Covered Intervals - Practice Coding Problems

Remove Covered Intervals - Problem

Array Sorting Medium

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

An interval [a, b) is covered by interval [c, d) if and only if c ≤ a and b ≤ d.

Return the number of remaining intervals after removing all covered intervals.

Input & Output

Example 1 — Basic Coverage

$ Input: intervals = [[1,4],[3,6],[2,8]]

› Output: 2

💡 Note: Interval [3,6] is covered by [2,8] because 2 ≤ 3 and 6 ≤ 8. So [1,4] and [2,8] remain.

Example 2 — No Coverage

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

› Output: 2

💡 Note: Neither interval covers the other: [1,4] doesn't cover [2,3] (4 > 3 but we need 3 ≤ 4), and [2,3] doesn't cover [1,4].

Example 3 — Multiple Covered

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

› Output: 1

💡 Note: [1,4] covers both [1,2] and [3,4]. Only [1,4] remains.

Constraints

1 ≤ intervals.length ≤ 1000
intervals[i].length == 2
0 ≤ li < ri ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of intervals [[1,4],[3,6],[2,8]]

Find Coverage

Identify that [3,6] is covered by [2,8]

Count Remaining

Return count of uncovered intervals: 2

Key Takeaway

🎯 Key Insight: Sorting by start point enables single-pass detection of covered intervals

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that sorting intervals by start point allows us to efficiently detect coverage in a single pass. The optimal approach sorts intervals by start ascending and end descending, then scans to count uncovered intervals. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Compare every interval with every other interval to check coverage
Sort and Scan	O(n log n)	O(1)	Sort intervals by start point, then scan to find covered intervals

Brute Force — Algorithm Steps

Step 1: For each interval, compare with all other intervals
Step 2: Check if current interval is covered by any other
Step 3: Count intervals that are not covered

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare All Pairs

For each interval, check against all others

Check Coverage

See if any interval completely covers another

Count Uncovered

Count intervals not covered by any other

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int intervals[][2], int n) {
    bool covered[n];
    for (int i = 0; i < n; i++) covered[i] = false;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                // Check if intervals[i] is covered by intervals[j]
                if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1]) {
                    covered[i] = true;
                    break;
                }
            }
        }
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!covered[i]) count++;
    }
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int intervals[100][2];
    int n = 0;
    char *ptr = line + 1; // Skip first '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            intervals[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            intervals[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ']'
            n++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(intervals, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops comparing each interval with every other interval

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

18.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler