Merged Intervals

Question 1

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

TC:- O(n)
SC:- O(n)

Answer 1

Pseudo code:

1. If input size is less than 2 return the input as result.
2. Sort the intervals list order by start.
3. Initialize interval list for result.
4. Keep first interval start and end in int variable.
5. Iterate through intervals from 2nd interval.
   a. If first interval end is greater than second internal, update end with max of first and second interval end.
   b. Else create new interval with start and end value and add in result list.
6. In the last out side list create new interval with start and end value and add in result list.
7. Return result list.

Takeaways:-

1. Sort the given intervals in the begining
2. Use linked list to store the merged intervals and then use Arrays util to convert linked list to 2d array as return type. list.toArray(new int[list.size()][]);
3. For loop will process upto 2nd last merged interval.
4. Add the last interval outside of for loop.