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.

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.

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:
                pass
            else:
                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.

Tanishq Chaudhary

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