Merging line segments

Problem: Given a collection of intervals, write a function that returns the total non-overlapping range covered.

Input: [(0, 15), (11, 17), (10, 20), (45, 50)]
Output: [(0, 20), (45, 50)]

Visualization

(0,15) ---------------
(11,17)           -------
(10,20)          -------------------
(45,50)                                                   -----
                                                
result  ----------------------------                      -----
       0                          20                     45   50

When presented with this problem I wrote the following to solve it

My Solution

def find_overlaps(segments: list[tuple[int, int]]) -> list[tuple[int, int]]:
    simplified_segments = []
    for segment in segments:
        merged = False
        start, end = segment[0], segment[1]
        for i, current in enumerate(simplified_segments):
            current_start, current_end = current[0], current[1]
            if max(start, current_start) <= min(end, current_end):
                overlap = min(end, current_end) - max(start, current_start)
                simplified_segments[i] = (min(start, current_start), max(end, current_end))
                merged = True
                break
        if not merged:
            simplified_segments.append(segment)
    return simplified_segments

The core part is the check for overlapping done by the line max(start, current_start) <= min(end, current_end) Here I check for the start pair is before the lowest end point and if so then there is an overlap as in given two segments

• Segment 1: (0, 5)
• Segment 2: (4, 10)

That means max(0, 4) = 4 and min (5,10) = 5 and therefore Segment 2 starts before the end of Segment 1 and so the segment bounds can be combined. The amount of overlap between the two segments can be calculate with overlap = min(end, current_end) - max(start, current_start) using the example segments above that would be min(5, 10) = 5 - max(0, 4) = 4 giving an overlap of 1

Comparing with large language model (LLM) generated code which gave this back

LLM Solution

def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    # Sort intervals by their starting point
    intervals.sort(key=lambda x: x[0])
    merged = []

    for start, end in intervals:
        if not merged or merged[-1][1] < start:
            # No overlap, add the interval
            merged.append((start, end))
        else:
            # Overlap, merge the intervals
            merged[-1] = (merged[-1][0], max(merged[-1][1], end))

    return merged

There is a sort of the elements to start with which I didn't do and the in place movement of is a bit odd to me, but it works. Working it out it seems the dependency on the sort is the key difference between what I wrote as I do in place range expansion with the inner for loop and the generated code assumes sorted start points so it can slowly build the intervals in order. Interesting approach I am curious where this was copied from though because missing some context here obviously.