Leetcode 56 - Merge Intervals

Prompt: Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example:

Input: intervals = [[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].

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution: We can use a temp list and pop all the intervals from the intervals list and put them in the temp list. Before we put intervals in the temp list, we have to loop through all intervals in the temp list and see if either the start or end of the current interval is overlapping with any intervals in the temp list. If it is overlapping, then we can increase the start or end of the set intervals with the current interval. In order to see if an interval A is overlapping with interval B, we can see if the start or end of A is greater than B start and less than B end. The runtime for this solution is O(n²)