LeetCode #56: Merge Intervals

https://leetcode.com/problems/merge-intervals/description/

In this problem, we have to merge overlapping intervals in a list. We are given a list of intervals where each interval is represented by a pair of start and end times. We have to merge all overlapping intervals and return the list of non-overlapping intervals.

We can approach this problem by following the below steps:

• Sort the intervals based on their start time
• Initialize an empty list for the merged intervals
• Traverse through the intervals and compare their start and end times with the previous intervals in the merged list
• If the current interval’s start time is greater than the previous interval’s end time, then add the current interval to the merged list
• Else, merge the current interval with the previous interval by updating the end time of the previous interval
• Return the merged list

Here is the solution in python3:

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        merged = []
        
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
                
        return merged

Time and Space Complexity

The time complexity of the solution is O(nlogn), where n is the number of intervals. This is due to the time taken for sorting the intervals using the built-in Python sort function. After sorting, the intervals are traversed once to merge them if they overlap.

The space complexity is O(n), where n is the number of intervals. This is due to the additional space needed to store the merged intervals in the output list. In the worst case scenario where no intervals can be merged, the size of the output list would be equal to the size of the input list.