LeetCode: 56 Merge Intervals

LeetCode Problem: 56. Merge Intervals

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

Problem Description:

Given a collection of intervals, merge all overlapping intervals.

Example:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

Original Code (Using Sorting and Merging):

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda pair: pair[0])  # Sort intervals based on the start time
        res = [intervals[0]]  # Initialize the result with the first interval

        for start, end in intervals:
            last_end = res[-1][1]  # Get the end of the last added interval
            if start <= last_end:  # Check for overlap
                res[-1][1] = max(last_end, end)  # Merge intervals by updating the end
            else:
                res.append([start, end])  # No overlap, add the current interval to the result

        return res  # Return the merged intervals

Line-by-Line Explanation and Example Execution:

1. class Solution:

   • Defines the Solution class.

2. def merge(self, intervals: List[List[int]]) -> List[List[int]]:

   • Defines the merge method that takes a list of intervals and returns the merged intervals.

3. intervals.sort(key=lambda pair: pair[0])

   • Sorts the intervals based on their starting times. This allows us to easily check for overlaps.

4. res = [intervals[0]]

   • Initializes the result list res with the first interval, as it will serve as the base for merging.

5. for start, end in intervals:

   • Iterates through each interval in the sorted list.

6. last_end = res[-1][1]

   • Retrieves the end of the last interval in the result list to compare with the current interval.

7. if start <= last_end:

   • Checks if the current interval overlaps with the last interval in res.

8. res[-1][1] = max(last_end, end)

   • If there is an overlap, merges the current interval with the last interval by updating the end to be the maximum of both ends.

9. else:

   • If there is no overlap, the current interval is appended to the result list:

     res.append([start, end])

10. return res

    • Returns the list of merged intervals.

Example Execution:

Assuming we have the following input:

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

1. Sorting:

   • The sorted intervals will be: [[1, 3], [2, 6], [8, 10], [15, 18]].

2. Initial Result:

   • Start with res = [[1, 3]].

3. First Iteration:

   • Current interval: [2, 6]
   • last_end = 3. Since 2 <= 3, we merge:
     • res = [[1, 6]].

4. Second Iteration:

   • Current interval: [8, 10]
   • last_end = 6. Since 8 > 6, we add it:
     • res = [[1, 6], [8, 10]].

5. Third Iteration:

   • Current interval: [15, 18]
   • last_end = 10. Since 15 > 10, we add it:
     • res = [[1, 6], [8, 10], [15, 18]].

Time Complexity Analysis:

• Time Complexity: O(n log n)
  • The primary time complexity comes from sorting the intervals, which takes O(n log n). The merging process itself is O(n).

Space Complexity Analysis:

• Space Complexity: O(n)
  • In the worst case, if all intervals are non-overlapping, the result list could contain all the original intervals.

Tips and Warnings:

1. Edge Cases:

   • Consider cases where the input list is empty or contains only one interval.

2. Understanding Merging Logic:

   • Ensure you understand how intervals are merged based on their start and end times.

3. In-place Modifications:

   • The solution uses an auxiliary list to store results, but it could be modified to operate in-place for space efficiency if needed.

Summary

• Sorting and Merging Method: Efficiently merges overlapping intervals with a time complexity of O(n log n) and space complexity of O(n).
• Clear and Understandable: The code is straightforward and easy to follow, making it suitable for this type of problem.

Application Tips

1. Choose Appropriate Methods:

   • Select the method best suited to specific problem requirements to ensure efficiency and readability.

2. Handle Edge Cases:

   • Always consider edge cases in algorithm design to avoid potential errors.

3. Optimize Space Usage:

   • When handling large datasets, consider using space-efficient algorithms.