Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode 1288: Remove Covered Intervals

By Duncan Smith Jan 20 0

LeetCode 2021

Problem

LeetCode 1288: Remove Covered Intervals (Medium)

Problem statement: Given a list of intervals, return the number of intervals that are not covered by another interval in the list.

For this problem, think of an interval as a segment of the number line with integer starting and ending points. For example, the interval $(-1, 1)$ is a segment of length $2$ centered at $0$.

Interval $(c,d)$ covers interval $(a,b)$ iff $c \leq a$ and $b \leq d$. Intuitively, this means that no point on $(a,b)$ is outside of the range covered by $(c,d)$.

Note that if one interval’s end point is the same as another interval’s start point, neither interval covers the other. For example, intervals $(0,2)$ and $(2,4)$ would contribute two intervals to the count. But $(0,2)$ and $(1,2)$ would only contribute one interval to the count, since the first interval covers the second. In a third case, $(0,2)$ and $(1,3)$ would count as two intervals. Although the intervals overlap, neither interval completely covers the other.

Solution

The solution described here is based on this solution by lee215, a well-known contributor to the LeetCode discussion forums.

Algorithm

  • Sort the intervals by start position. This allows us to make one pass through the list without backtracking or using any data structure besides an array.
  • Maintain a comparison interval $(c,d)$ that stores the most recent interval that is not covered by another interval. Note that $(c,d)$ is not necessarily an interval in the input list.
  • For each interval $(a,b)$ in the input list:
    • If $a > c$ and $b > d$, then some of $(a,b)$ is to the right of comparison interval $(c,d)$, and some of comparison interval $(c,d)$ is to the left of $(a,b)$. This means neither interval completely covers the other. Therefore, we can increment the interval count by one. We also need to let $c=a$ to advance the comparison interval start point.
    • Let $d=\max(d,b)$ to advance the comparison interval end point.
  • Return the interval count.

Notes

One way to see why this algorithm works is to consider all the ways that interval $(a,b)$ and comparison interval $(c,d)$ can be positioned relative to each other. For the starting endpoints of each interval, the possibilities are $a<c$, $a=c$, and $a>c$. Similarly, for the ending endpoints, we have $b<d$, $b=d$, and $b>d$. Since there are three possibilities for each of the two endpoints, there are a total of $3 \times 3 = 9$ combinations.

But because we start the algorithm by sorting the intervals by start point, we can eliminate $a<c$, since each interval must start at least even with the previous interval (i.e., the start points are nondecreasing). This means there are only $2 \times 3 = 6$ cases that can occur. Here are those cases:

(1) $a>c$ and $b>d$

    c ---------- d
    a   ---------- b

This is the configuration detected by the if statement in the algorithm. Neither interval covers the other, so we increment count and $(a,b)$ becomes the new comparison interval.

(2) $a>c$ and $b=d$

    c ---------- d
    a   -------- b

$(a,b)$ is completely covered by $(c,d)$, so we skip it without incrementing count.

(3) $a>c$ and $b<d$

    c ---------- d
    a   ------   b

This is a similar configuration to (2). $(a,b)$ is completely covered.

(4) $a=c$ and $b>d$

    c ---------- d
    a ------------ b

As with the other cases, we don’t go into the if block so we don’t increment count for this case. But this time it’s because the new interval $(a,b)$ covers the comparison interval $(c,d)$ (the reverse of cases (2) and (3)). This is why it’s important to set $d=\max(d,b)$ outside the if block. Even when there’s not a new interval to count, we need the right endpoint of the comparison interval to be as far right as possible.

(5) $a=c$ and $b=d$

    c ------------ d
    a ------------ b

The new interval is identical to the comparison interval, so we don’t count it.

(6) $a=c$ and $b<d$

    c ------------ d
    a ----------   b

This is similar to (3) and (4). $(a,b)$ is completely covered, so we don’t count it.

After considering all six cases, we can see that we only need to count a new interval in one case, the first one. In the other cases, all we need to do is possibly adjust the right endpoint of the comparison interval.

Code

Remove Covered Intervals on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • 2022 in Review: Content Bots
  • 2021 in Review: Thoughts on Solving Programming Puzzles
  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • LeetCode Tip 11: How To Use Spaced Repetition (Part 1) March 22, 2023
  • LeetCode Tip 10: Planning a Spaced Repetition Schedule March 15, 2023
  • Book Review – Algorithmic Thinking: A Problem-Based Introduction, Second Edition March 9, 2023
  • LeetCode Tip 9: Spaced Repetition March 8, 2023
  • LeetCode Tip 8: Anatomy of a Model Solution March 1, 2023
  • LeetCode Tip 7: How to Write a Model Solution February 22, 2023
  • LeetCode Tip 6: Model Solutions February 15, 2023
  • LeetCode Tip 5: Choosing a Model Problem February 8, 2023
  • LeetCode Tip 4: Model Problems February 1, 2023
  • LeetCode Tip 3: A Goal for LeetCode Practice January 25, 2023
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2023 Duncan Smith