How can I efficiently merge overlapping intervals in a list of tuples in Python?

I not that good at python but I think this will help you, try this code:

def merge_intervals(intervals):
"""
Merge overlapping intervals into a single interval.

Args:
- intervals (list of tuples): List of intervals represented as tuples (start, end).

Returns:
- merged (list of tuples): List of non-overlapping intervals after merging.

Example:
>>> merge_intervals([(1, 3), (2, 4), (5, 7), (6, 8)])
[(1, 4), (5, 8)]
"""
sorted_intervals = sorted(intervals, key=lambda x: x[0])
merged = []
for interval in sorted_intervals:
    if not merged or merged[-1][1] < interval[0]:
        merged.append(interval)
    else:
        merged[-1] = (merged[-1][0], max(merged[-1][1], interval[1]))
return merged
my_intervals = [(1, 3), (2, 4), (5, 7), (6, 8)]
print(merge_intervals(my_intervals))d

And yeah, the output at least for me is exactly as you want:

[(1, 4), (5, 8)]

let me know if worked.

I see nothing wrong with your code, it is quite pythonic (simple, clear and readable), there is no sugar syntax I can think of to improve your code, no comprehension, functional style (map, filter, reduce...) that can help in this way.

To address your efficiency question, here is a vectorized version of your task using numpy.

import numpy as np

my_intervals = [(1, 3), (2, 4), (5, 7), (6, 8), (9, 11), (10, 12), (11, 12), (1,2)]
my_intervals = np.array(my_intervals)

my_intervals.sort(axis=0)

start_bounds = my_intervals[:,0]
end_bounds = my_intervals[:,1]

start_bounds_filter = ~np.convolve(end_bounds >= np.concatenate([start_bounds[1:], [np.inf]]), [False, True], mode='same')
end_bounds_filter = np.flip(~np.convolve(np.flip(start_bounds <= np.concatenate([[-np.inf], end_bounds[:-1]])), [False, True], mode='same'))

result = np.vstack([start_bounds[start_bounds_filter], end_bounds[end_bounds_filter]]).T.tolist()

Using Jupyter %%timeit for benchmarking, you already see that your implentation is much faster (in the order of ns while the vectorized one in the order of micro seconds), and I also tried using the numba library for a JIT version of your implementation which had even worst results. Scaling the sample does not turn the tables in the performance.

Loop solution: Vectorized solution:

In summary, in this case simple is best (in clarity and performance), be confident it is readable and scales well.

You can do this linearly O(n) without sort.

from collections import defaultdict
from typing import Iterable

my_intervals = [(1, 3), (2, 4), (5, 7), (6, 8), (2, 3), (2, 3), (2, 4)]


def merger(intervals: Sequence[tuple]) -> Iterable[tuple]:
    max_val = max(i[1] for i in intervals)
    min_val = min(i[0] for i in intervals)
    breakpoints = [0] * (max_val - min_val + 1)

    min_val, max_val = intervals[0]
    for start, end in intervals:
        if end < start:
            raise ValueError(f"Improper interval: {start} !<= {end}")
        breakpoints[start - min_val] += 1
        breakpoints[end - min_val] -= 1
        min_val = start if start < min_val else min_val
        max_val = end if end > max_val else max_val

    res = []
    current_start = min_val
    marker = 0  # marker is > 0 when in an interval, else "dead space"
    for i in range(min_val, max_val + 1):
        marker += breakpoints[i - min_val]
        if current_start and marker == 0:  # close the interval
            end = i
            res.append((current_start, end))
            current_start = None
        elif not current_start and marker > 0:  # start an interval
            current_start = i
    return res

Output:

[(1, 4), (5, 8)]