Disjoint Intervals | InterviewBit | Solution Explained

I explain the solution to Disjoint Intervals on InterviewBit using visuals in simple words.

0. Disjoint Intervals: Problem Discussion

0.0. IO Format

  • input:
    • Given a list of intervals: [start, end].
  • output:
    • Find the length of the maximal set of mutually disjoint intervals.
  • Constraints:
    • 1 ≤ N ≤ 1e5
    • 1 ≤ A[i][0] ≤ A[i][1] ≤ 1e9

0.1. Examples

1. Disjoint Intervals : Observations & Logic

1.0. Intuitions

Let’s take the test case in the problem statement and start working upon a solution. From the explanation of the test case above, there are two possible ways we can select these intervals.

Disjoint Intervals: test case explanation
Disjoint Intervals: test case explanation

We see that in the first possibility, we select the interval [1,2] and we have to skip the interval [2,10]. That is because 2 is common, so we can’t select [2,10] after we select [1,2]. Then we move through the array and find [4,6], which is okay because it is mutually disjoint, as we can see from the visual. Thus, the answer is 2.

Note an interesting point: because we selected [1,2], all the changes we had later on, came as a result of the selection.

In the second possibility, we select [2,10] instead of [1,2] and so we can’t select anything else. Thus, the answer is 1.

Since the max of both the possibilities is 2, that becomes our final answer.

1.1. Start early or end early?

We have a pretty solid understanding of the problem, but now how do we proceed with the solution? Well, let’s take another test case and try it out.

Disjoint Intervals: a more involved test case explanation
Disjoint Intervals: a more involved test case explanation

We see that selecting [1,4] versus [2,3] made all the difference in the case above. What does that mean? Let’s try to find the reason behind the success of [2,3].

One possibility is that intervals like [2,3] which start later than [1,4] give a better answer. OR, it might be that intervals which end early – again, like [2,3] give a better answer.

At this point, it’ll be too early to say and well, its just a heuristic.

So, what do we pick? “start later” OR “end early”? Think about it yourself first. Use your intuition!

1.2. End it now

Intuitively speaking, the intervals which end early are better. In fact, intervals that start early and end early are good. Why?

The problem asks us to maximize the number of mutually disjoint intervals. If we can get shorter intervals – the ones which start and end early, then we have more space available for intervals to come into the picture later on!

On the flip side, if an intervals ends later, it’ll prevent other intervals from joining the party.

The only big issue that glares at us is that this is just a heuristic. What is the guarantee that the solution which picks intervals greedily by their end times is … indeed optimal?

1.3. Proof

The proof is left up to the reader, because the writer got too lazy to do it right now.

Remind me in the comments down below? Thanks.

2. Disjoint Intervals : Optimized Implementation

2.0. Code

class Solution:
    # @param A : list of list of integers
    # @return an integer
    def solve(self, A):
        A.sort(key=lambda x: x[1])
        prev_s, prev_e = A[0]
        count = 1
        for s, e in A:
            if s <= prev_e:
                prev_s, prev_e = s, e
                count += 1
        return count

2.1. Complexity Analysis

  • Time: O(NlogN), for the sorting
  • Space: O(algo), since different languages use different algorithms that have different space complexities. Worst case, we take O(NlogN), since that is what vanilla merge sort uses.
Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.


    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

      A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

      Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

      To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

      Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

      This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

      Understanding why solar energy consultants assist clients via Matthew D’Agati.
      Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.