Disjoint Intervals

Moderate

0/80

Average time to solve is 30m

Contributed by

5 upvotes

Asked in companies

Problem statement

Given a 2D array of size Nx2 which contains a set of ‘N’ intervals. Each interval contains a starting point and an ending point. You need to find the size of the maximal set of mutually disjoint intervals.

Two sets [a,b] and [c,d] are disjoint intervals if there is no common point between these two intervals.

For example: [5,7] and [8,10] are disjoint intervals but the intervals [5,7] and [7,10] is not a disjoint interval as they have a common point, 7 in them.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next 2*T represents the ‘T’ test cases.

The first line of each test case contains an integer ‘n’ denoting the number of intervals.

The next ‘n’ lines of each test case contain two space-separated non-negative integers denoting the starting and end of an interval respectively.

Output Format :

For each test case, return the size of the maximal set of mutually disjoint sets.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= n <= 10^4
1 <= a < b <= 10^9 
Where ‘T’ is the total number of test cases, ‘n’ is the number of intervals  and ‘a’, ‘b’ are the starting and ending of an interval.

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

2
3

Explanation of Sample Input 1 :

Test case 1 :
The intervals [1,6] and [2,4] overlap, in this case, we should select [2,4] because if we include [1,6], then we can not select [6,8]. So the desired intervals are [2,4] and [6,8].

Test case 2 :
The intervals [1,5] and [2,3] overlap, in this case, we should select [2,3] because if we include [1,5], then we can not select [4,7]. So the selected intervals are [2,3], [4,7] and [8,9].

Sample Input 2 :

Sample Output 2 :

2
1

Hint 1

Hint 2

Sort the intervals by their starting point.

Approaches (2)

Approach 1

Approach 2

Dynamic Programming

Sort the given interval set by their starting points.
Traverse the sorted set from the start and for each interval calculate the maximal number of disjoint intervals ending before it.
The recurrence relation is dp[i] = 1 + max(dp[j]) (0 <= j < i and ending(j)<starting(i))
The answer is max(dp[0], dp[1], dp[2],.....,dp[n-1]).

Time Complexity

O(N^2), where ‘N’ is the number of intervals in the given set.

For each interval, we have to iterate all the intervals starting before it.

Space Complexity

O(N), where ‘N’ is the number of intervals in the sorted set.

We have to declare a dp array of size ‘N’.

(100% EXP penalty)

Disjoint Intervals

Console