issue #127 Solution

[rakeshmahato]

Problem Statement

[Leet Code Problem] (https://leetcode.com/problems/merge-intervals)

Given an array (list) of interval pairs as input where each interval has a start and end timestamp. The input array is sorted by starting timestamps. Merge overlapping intervals and return a new output array.

Overlapping Intervals (1, 5), (3, 7), (4, 6), (6, 9) Merged to one big interval as (1, 9).

Solution

This problem can be solved in a simple linear Scan algorithm. We know that input is sorted by starting timestamps. Approach are following: List of input intervals is given, keep merged intervals in the output list. For each interval in the input list: If the input interval is overlapping with the last interval in output list then we’ll merge these two intervals and update the last interval of output list with merged interval. Otherwise, we’ll add an input interval to the output list.

The runtime complexity of this solution is linear, O(n). The memory complexity of this solution is linear, O(n).