1288. Remove Covered Intervals LeetCode Solution

In this guide, you will get 1288. Remove Covered Intervals LeetCode Solution with the best time and space complexity. The solution to Remove Covered Intervals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Remove Covered Intervals solution in C++
Remove Covered Intervals solution in Java
Remove Covered Intervals solution in Python
Additional Resources

1288. Remove Covered Intervals LeetCode Solution image

Problem Statement of Remove Covered Intervals

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.
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 <= li < ri <= 105
All the given intervals are unique.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(1)

1288. Remove Covered Intervals LeetCode Solution in C++

class Solution {
 public:
  int removeCoveredIntervals(vector<vector<int>>& intervals) {
    // If the two intervals have the same `start`, put the one with a larger
    // `end` first.
    ranges::sort(intervals, [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });

    int ans = 0;
    int prevEnd = 0;

    for (const vector<int>& interval : intervals)
      // The current interval is not covered by the previous one.
      if (prevEnd < interval[1]) {
        prevEnd = interval[1];
        ++ans;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

1288. Remove Covered Intervals LeetCode Solution in Java

class Solution {
  public int removeCoveredIntervals(int[][] intervals) {
    // If the two intervals have the same `start`, put the one with a larger
    // `end` first.
    Arrays.sort(intervals,
                (a, b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]));

    int ans = 0;
    int prevEnd = 0;

    for (int[] interval : intervals)
      // The current interval is not covered by the previous one.
      if (prevEnd < interval[1]) {
        prevEnd = interval[1];
        ++ans;
      }

    return ans;
  }
}
// code provided by PROGIEZ

1288. Remove Covered Intervals LeetCode Solution in Python

class Solution:
  def removeCoveredIntervals(self, intervals: list[list[int]]) -> int:
    ans = 0
    prevEnd = 0

    # If the two intervals have the same `start`, put the one with a larger
    # `end` first.
    for _, end in sorted(intervals, key=lambda x: (x[0], -x[1])):
      # The current interval is not covered by the previous one.
      if prevEnd < end:
        prevEnd = end
        ans += 1

    return ans
 # code by PROGIEZ