Merge overlapping intervals

Sort intervals by start, then merge any that overlap with the one before it in a single scan.

The idea

Once intervals are sorted by start, an overlap can only involve the most recently merged interval: if the next interval starts before that one ends, fold it in by stretching the end; otherwise it begins a new, separate interval.

Code

public static List<(int, int)> MergeIntervals(List<(int, int)> intervals) {
    intervals.Sort((x, y) => x.Item1 - y.Item1);
    var merged = new List<(int, int)>();
    foreach (var cur in intervals) {
        if (merged.Count > 0 && cur.Item1 <= merged[^1].Item2) {
            var last = merged[^1];
            merged[^1] = (last.Item1, Math.Max(last.Item2, cur.Item2));
        } else {
            merged.Add(cur);
        }
    }
    return merged;
}

Tips

• Only the end of the last merged interval needs comparing - after sorting by start, nothing earlier could still overlap.
• Watch for touching intervals like [1, 3] and [3, 5]: whether those count as overlapping depends on the problem; this version merges them with <=.

In the .NET library

Without sorting first, every interval would need comparing against every other one, an O(n²) check instead of one O(n log n) scan.