DDSA Solutions

1288. Remove Covered Intervals

MediumView on LeetCode
ArraySortingGreedy
Time: O(n log n)
Space: O(1)

Problem Overview

Interval [a,b] is covered by another if that other starts no later and ends no earlier.

Intuition

Interval [a,b] is covered by another if that other starts no later and ends no earlier. After sorting by start ascending and end descending, any interval fully covered by a previous one cannot extend the maximum end — so we only count intervals that push the farthest end forward.

Algorithm

  1. 1Sort intervals: primary key start ascending, secondary key end descending.
  2. 2Track prevEnd = 0 and answer = 0.
  3. 3For each [start, end]: if end > prevEnd, this interval is not covered — increment answer and set prevEnd = end.
  4. 4Return answer.

Example Walkthrough

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

  1. 1.After sort: [[1,4],[3,6],[2,8]].
  2. 2.[1,4]: end 4 > 0 → count 1, prevEnd = 4.
  3. 3.[3,6]: end 6 > 4 → count 2, prevEnd = 6.
  4. 4.[2,8]: end 8 > 6 → count 3, prevEnd = 8.

Output: 3

Common Pitfalls

  • •Sort by end descending when starts tie — otherwise a shorter interval at the same start can hide a longer covering one.
  • •Use end > prevEnd, not start > prevEnd; coverage is about the right endpoint.
1288.cs
C#
// Approach: Sort by start ascending; for equal starts, longer intervals first. Scan and count
// only intervals whose end extends past the farthest end seen so far.
// Time: O(n log n) Space: O(1) extra (sort in-place)
public class Solution
{
    public int RemoveCoveredIntervals(int[][] intervals)
    {
        Array.Sort(intervals, (a, b) =>
        {
            int cmp = a[0].CompareTo(b[0]);
            if (cmp == 0)
                return b[1].CompareTo(a[1]);

            return cmp;
        });

        int ans = 0;
        int prevEnd = 0;

        foreach (var interval in intervals)
        {
            if (prevEnd < interval[1])
            {
                prevEnd = interval[1];
                ans++;
            }
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems