Merge Clashing Intervals JPMC

The question appeared in the coding test taken by JP Morgan Chase in one of the placement drives.

Task :- Given a list of intervals(starting time,ending time), merge all the clashing intervals and return the sorted non-clashing intervals.

For eg: intervals = [ (1, 5), (7, 11),(15, 20), (3, 9) ]

Answer = [ (1, 11), (15, 20) ]

First we merge intervals (1, 5) and (3, 9) and after merging we get the interval (1, 9).

Then this merged interval clashes with (7, 11) and we merge these two to get interval (1, 11). No other intervals are clashing, so we return these intervals in sorted order.

Brute Force Approach :- We can take each interval and check with every other interval whether it clashes or not. If it does then we merge these two and proceed. We keep on doing this till we do not get an iteration where no intervals were merged which means there are no more clashing intervals. Then we sort them and return the remaining intervals.

The time complexity of this approach would be O(N²) and is not enough to pass all the test cases.

Efficient Approach:- First we sort the intervals based on their starting time. Doing this would make sure that if two intervals are clashing they would be adjacent in the sorted list.

We can keep a stack in which we put all the intervals that are not clashing. So at first we put the first interval in the stack. Now we take the second interval to check whether that interval clashes with the interval in the stack top. If it clashes we remove the interval from stack, merge the two intervals and put the merged interval in the stack.

If the current interval doesn’t clash with the stack top we simply put that in the stack.

We keep on doing this for every interval in the sorted list.

To merge two intervals let’s say first = (1, 7), second = (3, 9)

Merged interval = ( starting time of first , ending time of second )

The above condition do not guarantee a correct answer.

Because the ending time of first can be greater than that of second

For eg: first = (1, 7), second = (3, 5) then the merged interval should be (1, 7)

Hence, Merged interval = ( start time of first, max( end time of first, end time of second) )

Code:-