Remove Covered Intervals Solution in C++

Explore More Solutions
Java Solution
Python Solution

Problem Description

Welcome to the world of intervals, where overlapping is not just a suggestion but a way of life! The problem at hand, “Remove Covered Intervals,” is like trying to find the best spot on a crowded beach. You know, the one where you can lay your towel without someone else’s umbrella blocking your sun.

In this problem, you’re given a list of intervals, and your task is to determine how many of these intervals are not covered by others. An interval [a, b] is considered covered by another interval [c, d] if c <= a and b <= d. So, if you have a friend who insists on bringing their own beach umbrella that covers your entire sunbathing area, you might want to rethink your friendship!

Code Solution


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

    int ans = 0;
    int prevEnd = 0;

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

    return ans;
  }
};

Approach Explanation

The approach taken in this solution is as elegant as a well-executed dance move. First, we sort the intervals based on their starting points. If two intervals start at the same point, we prioritize the one that ends later. This way, we can easily identify which intervals are covered as we iterate through the sorted list.

As we traverse the sorted intervals, we keep track of the end of the last interval that was not covered. If the current interval's end is greater than the last recorded end, it means this interval is not covered, and we count it.

Time and Space Complexity

Time Complexity: O(n log n) due to the sorting step, where n is the number of intervals.
Space Complexity: O(1) if we ignore the space used by the input, as we are only using a few extra variables.

Real-World Example

Imagine you're at a concert, and everyone is trying to get the best view of the stage. Some people are standing in front of you, blocking your view. The "Remove Covered Intervals" problem is like figuring out how many people you can actually see without someone else's head getting in the way. You want to count only those who are standing tall and proud, not those who are just hiding behind someone else's taller friend!