Merge Intervals - Python Solution

1. Introduction

The "Merge Intervals" problem is a common challenge in computational geometry and array manipulation. It involves merging overlapping intervals in a list, a task frequently encountered in areas like calendar event scheduling. This problem tests one’s ability to analyze and merge ranges efficiently.

Problem

Given an array of intervals where each interval is defined as [starti, endi], the task is to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

2. Solution Steps

1. Sort the intervals array based on the start times.

2. Initialize a list merged to hold the merged intervals.

3. Iterate through the sorted intervals.

4. For each interval, if the merged list is empty or if the current interval does not overlap with the last interval in merged, simply append it.

5. If there is an overlap, merge the current interval with the last interval in merged by updating the end time.

6. Return the merged list.

3. Code Program

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    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

# Example Usage
print(merge([[1,3],[2,6],[8,10],[15,18]]))  # Output: [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]]))                 # Output: [[1,5]]

Output:

[[1,6],[8,10],[15,18]]
[[1,5]]

Explanation:

1. Sorting: Intervals are sorted based on their start times to align overlaps.

2. Merging Logic: Determines whether to merge intervals or add them as is.

3. Overlap Check: Checks if the current interval overlaps with the last one in merged.

4. Update Merged Intervals: If there's an overlap, updates the end time of the last interval in merged.

5. Efficient Solution: Achieves O(n log n) time complexity due to sorting.

6. Applicability: Demonstrates an approach to handling and merging ranges, useful in event scheduling and range queries.