Problem of The Day: Merge Intervals

5 min read 1048 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        res = []
        sorted_intervals = sorted(intervals)
        for i, interval in enumerate(sorted_intervals):
            start, end = interval
            if not res:
                res.append([start, end])
            else:
                if start <= res[-1][1]:
                    res[-1][1] = max(res[-1][1], end)
                else:
                    res.append([start, end])
        return res

public class Solution {
    public int[][] Merge(int[][] intervals) {
        List<List<int>> res = new List<List<int>>();
        Array.Sort(intervals, (a,b) => a[0].CompareTo(b[0]));
        foreach (var interval in intervals) {
            if (res.Count == 0) {
                res.Add(new List<int>(interval));
            } else {
                int start = interval[0];
                int end = interval[1];
                int lastIndex = res.Count - 1;
                int prevEnd = res[lastIndex][1];
                if (start <= prevEnd) {
                    res[lastIndex][1] = Math.Max(res[lastIndex][1], end);
                } else {
                    res.Add(new List<int>(interval));
                }
            }
        }

        return res.Select(x => x.ToArray()).ToArray();
    }
}

Time: O(nlogn) Space: O(n)

Editorial

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

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

        merged = []
        for interval in intervals:
            # if the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # otherwise, there is overlap, so we merge the current and previous
                # intervals.
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

public class Solution {
    public int[][] Merge(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        LinkedList<int[]> merged = new LinkedList<int[]>();
        foreach (int[] interval in intervals) {
            // if the list of merged intervals is empty or if the current
            // interval does not overlap with the previous, append it
            if (merged.Count == 0 || merged.Last.Value[1] < interval[0]) {
                merged.AddLast(interval);
            }
            // otherwise, there is overlap, so we merge the current and previous
            // intervals
            else {
                merged.Last.Value[1] =
                    Math.Max(merged.Last.Value[1], interval[1]);
            }
        }

        return merged.ToArray();
    }
}

public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals.Length <= 1) return intervals;

        // 1. Sort by start time
        // Using CompareTo is safer than subtraction (prevents integer overflow)
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

        List<int[]> merged = new List<int[]>();

        foreach (var current in intervals) {
            // If merged is empty or no overlap, add current
            // "no overlap" means: current start > previous end
            if (merged.Count == 0 || current[0] > merged[^1][1]) {
                merged.Add(current);
            }
            else {
                // Overlap exists: update the end time of the last interval
                merged[^1][1] = Math.Max(merged[^1][1], current[1]);
            }
        }

        return merged.ToArray();
    }
}