# Merge Intervals **Difficulty:** MEDIUM [External](https://leetcode.com/problems/merge-intervals) Canonical: https://scaleengineer.com/dsa/problems/merge-intervals **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array **Companies:** [AMD](https://scaleengineer.com/companies/amd), [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Airbnb](https://scaleengineer.com/companies/airbnb), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cadence](https://scaleengineer.com/companies/cadence), [Cisco](https://scaleengineer.com/companies/cisco), [Deloitte](https://scaleengineer.com/companies/deloitte), [Docusign](https://scaleengineer.com/companies/docusign), [Dropbox](https://scaleengineer.com/companies/dropbox), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Expedia](https://scaleengineer.com/companies/expedia), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Hubspot](https://scaleengineer.com/companies/hubspot), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nielsen](https://scaleengineer.com/companies/nielsen), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Ozon](https://scaleengineer.com/companies/ozon), [PayPal](https://scaleengineer.com/companies/paypal), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Roblox](https://scaleengineer.com/companies/roblox), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [Zoho](https://scaleengineer.com/companies/zoho), [athenahealth](https://scaleengineer.com/companies/athenahealth), [Capital One](https://scaleengineer.com/companies/capital-one), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Turing](https://scaleengineer.com/companies/turing), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [Disney](https://scaleengineer.com/companies/disney), [Media.net](https://scaleengineer.com/companies/media.net), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zepto](https://scaleengineer.com/companies/zepto), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Databricks](https://scaleengineer.com/companies/databricks), [X](https://scaleengineer.com/companies/x), [razorpay](https://scaleengineer.com/companies/razorpay), [Nextdoor](https://scaleengineer.com/companies/nextdoor), [Anduril](https://scaleengineer.com/companies/anduril), [Tencent](https://scaleengineer.com/companies/tencent), [Grammarly](https://scaleengineer.com/companies/grammarly), [IXL](https://scaleengineer.com/companies/ixl), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Rivian](https://scaleengineer.com/companies/rivian), [Applied Intuition](https://scaleengineer.com/companies/applied-intuition), [Instacart](https://scaleengineer.com/companies/instacart), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [Workday](https://scaleengineer.com/companies/workday), [Ripple](https://scaleengineer.com/companies/ripple), [CARS24](https://scaleengineer.com/companies/cars24), [Cruise](https://scaleengineer.com/companies/cruise), [Grubhub](https://scaleengineer.com/companies/grubhub), [Moveworks](https://scaleengineer.com/companies/moveworks), [Netskope](https://scaleengineer.com/companies/netskope), [Okta](https://scaleengineer.com/companies/okta), [Synopsys](https://scaleengineer.com/companies/synopsys), [Tesco](https://scaleengineer.com/companies/tesco), [Zalando](https://scaleengineer.com/companies/zalando) --- ## Problem Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return _an array of the non-overlapping intervals that cover all the intervals in the input_. **Example 1:** **Input:** intervals = [[1,3],[2,6],[8,10],[15,18]] **Output:** [[1,6],[8,10],[15,18]] **Explanation:** Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. **Example 2:** **Input:** intervals = [[1,4],[4,5]] **Output:** [[1,5]] **Explanation:** Intervals [1,4] and [4,5] are considered overlapping. **Constraints:** * `1 <= intervals.length <= 104` * `intervals[i].length == 2` * `0 <= starti <= endi <= 104` # Approaches ## Brute Force using Graph This approach models the problem as finding connected components in a graph. Each interval is represented as a node, and an edge connects two nodes if their corresponding intervals overlap. The core idea is that all intervals that can be merged together form a single connected component in this graph. By finding these components, we can merge all intervals within each one to get the final result. **Time:** O(N²) · **Space:** O(N²) **Pros:** Conceptually demonstrates the connectivity aspect of the problem. **Cons:** Highly inefficient with a time complexity of O(N²).; Requires O(N²) space in the worst case to store the graph.; More complex to implement compared to the sorting approach. ### Explanation The algorithm proceeds in two main phases: graph construction and component merging. 1. **Graph Construction**: We first build an undirected graph. We iterate through every possible pair of intervals. For each pair, we check if they overlap. An overlap occurs if `interval1.start <= interval2.end` and `interval2.start <= interval1.end`. If they do, we add an edge between the nodes representing these two intervals. This process takes O(N²) time as it involves a nested loop over the N intervals. 2. **Component Merging**: After building the graph, we traverse it to find its connected components. We can use Depth-First Search (DFS) or Breadth-First Search (BFS). We maintain a `visited` array to keep track of nodes we've already processed. We iterate through all nodes from 0 to N-1. If a node hasn't been visited, we start a traversal from it. This traversal will find all nodes (intervals) in one connected component. For each component, we find the minimum start time and the maximum end time among all its intervals. This `[min_start, max_end]` pair forms a single merged interval. We add this to our result list and continue until all nodes have been visited. ```java import java.util.*; class Solution { public int[][] merge(int[][] intervals) { if (intervals.length <= 1) { return intervals; } int n = intervals.length; Map> graph = new HashMap<>(); for (int i = 0; i < n; i++) { graph.put(i, new ArrayList<>()); } // Build the graph by connecting overlapping intervals for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (overlaps(intervals[i], intervals[j])) { graph.get(i).add(j); graph.get(j).add(i); } } } List merged = new ArrayList<>(); boolean[] visited = new boolean[n]; // Find connected components and merge them for (int i = 0; i < n; i++) { if (!visited[i]) { List componentNodes = new ArrayList<>(); Stack stack = new Stack<>(); stack.push(i); visited[i] = true; // DFS to find all nodes in the component while (!stack.isEmpty()) { int node = stack.pop(); componentNodes.add(node); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; stack.push(neighbor); } } } // Merge all intervals in the found component merged.add(mergeComponent(componentNodes, intervals)); } } return merged.toArray(new int[merged.size()][]); } private boolean overlaps(int[] a, int[] b) { return a[0] <= b[1] && b[0] <= a[1]; } private int[] mergeComponent(List componentNodes, int[][] intervals) { int minStart = Integer.MAX_VALUE; int maxEnd = Integer.MIN_VALUE; for (int i : componentNodes) { minStart = Math.min(minStart, intervals[i][0]); maxEnd = Math.max(maxEnd, intervals[i][1]); } return new int[]{minStart, maxEnd}; } } ``` ### Algorithm - Build a graph where each interval is a node. - Add an edge between two nodes if their intervals overlap. This requires comparing every pair of intervals, taking O(N²) time. - Initialize a `visited` array and a result list. - Iterate through each interval (node). If a node hasn't been visited, it's part of a new connected component. - Start a graph traversal (like DFS or BFS) from this unvisited node to find all intervals in the component. - During the traversal, keep track of the minimum start and maximum end of all intervals in the current component. - Once the traversal for a component is complete, add the merged interval `[min_start, max_end]` to the result list. - Repeat until all nodes are visited. ## Optimal Approach using Sorting The most efficient way to solve this problem is by first sorting the intervals based on their start times. Once sorted, we can iterate through the intervals and merge them in a single pass. If the current interval overlaps with the previous merged interval, we combine them. Otherwise, we add the current interval as a new, separate interval to our result. **Time:** O(N log N) · **Space:** O(N) **Pros:** Very efficient with a time complexity of O(N log N), dominated by the sort.; Space efficient, using O(N) space for the result (or O(log N) for sorting stack space).; The logic is clean, simple, and easy to implement correctly. **Cons:** The primary cost is the initial sort. If the intervals were already sorted, the complexity would be O(N). ### Explanation The intuition behind this approach is that by sorting the intervals by their start points, we can guarantee that when we consider a new interval `i`, it will either overlap with the most recently added interval in our merged list or it won't overlap with any interval in the merged list. This simplifies the merging logic significantly. The algorithm is as follows: 1. Sort the input `intervals` array based on the start value of each interval. 2. Create a new list, `merged`, to store the final non-overlapping intervals. Add the very first interval from the sorted list to `merged`. 3. Iterate through the rest of the sorted intervals, starting from the second one. 4. For each `currentInterval`, look at the `lastInterval` in the `merged` list. 5. If `currentInterval.start` is less than or equal to `lastInterval.end`, it means there is an overlap. We then update `lastInterval.end` to be the maximum of its current end and `currentInterval.end`. This effectively merges the two intervals. 6. If there is no overlap (`currentInterval.start > lastInterval.end`), it means the `currentInterval` starts after the `lastInterval` ends, so they are distinct. We add the `currentInterval` as a new entry to our `merged` list. 7. Finally, we convert the `merged` list back into a 2D array and return it. ```java import java.util.Arrays; import java.util.LinkedList; import java.util.List; class Solution { public int[][] merge(int[][] intervals) { if (intervals.length <= 1) { return intervals; } // Sort intervals based on the start time Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); LinkedList merged = new LinkedList<>(); for (int[] interval : intervals) { // if the list of merged intervals is empty or if the current // interval does not overlap with the previous, simply append it. if (merged.isEmpty() || merged.getLast()[1] < interval[0]) { merged.add(interval); } // otherwise, there is overlap, so we merge the current and previous // intervals by updating the end of the last interval. else { merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]); } } return merged.toArray(new int[merged.size()][]); } } ``` ### Algorithm - If the input array has fewer than two intervals, return the original array as no merging is possible. - Sort the intervals based on their start times in ascending order. - Initialize a list, `merged`, to store the result. Add the first interval from the sorted array to `merged`. - Iterate through the sorted intervals from the second interval onwards. - For each `current` interval, compare it with the `last` interval in the `merged` list. - If the `current` interval overlaps with the `last` interval (i.e., `current[0] <= last[1]`), merge them by updating the end of the `last` interval to `max(last[1], current[1])`. - If they do not overlap, add the `current` interval to the `merged` list. - After the loop, convert the `merged` list back to a 2D array and return it. # Solutions ### CSharp ```csharp public class Solution { public int[][] Merge(int[][] intervals) { intervals = intervals.OrderBy(a => a[0]).ToArray(); var ans = new List < int[] > (); ans.Add(intervals[0]); for (int i = 1; i < intervals.Length; ++i) { if (ans[ans.Count - 1][1] < intervals[i][0]) { ans.Add(intervals[i]); } else { ans[ans.Count - 1][1] = Math.Max(ans[ans.Count - 1][1], intervals[i][1]); } } return ans.ToArray(); } } ``` ### Java ```java class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b)->a[0] - b[0]); List ans = new ArrayList<>(); ans.add(intervals[0]); for (int i = 1; i < intervals.length; ++i) { int s = intervals[i][0], e = intervals[i][1]; if (ans.get(ans.size() - 1)[1] < s) { ans.add(intervals[i]); } else { ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], e); } } return ans.toArray(new int[ans.size()][]); } } ``` ### JavaScript ```javascript /** * @param {number[][]} intervals * @return {number[][]} */ var merge = function ( intervals ) { intervals . sort (( a , b ) => a [ 0 ] - b [ 0 ]); const result = []; const n = intervals . length ; let i = 0 ; while ( i < n ) { const left = intervals [ i ][ 0 ]; let right = intervals [ i ][ 1 ]; while ( true ) { i ++ ; if ( i < n && right >= intervals [ i ][ 0 ]) { right = Math . max ( right , intervals [ i ][ 1 ]); } else { result . push ([ left , right ]); break ; } } } return result ; }; ``` ### CPP ```cpp class Solution { public: vector> merge(vector> &intervals) { sort(intervals.begin(), intervals.end()); vector> ans; ans.emplace_back(intervals[0]); for (int i = 1; i < intervals.size(); ++i) { if (ans.back()[1] < intervals[i][0]) { ans.emplace_back(intervals[i]); } else { ans.back()[1] = max(ans.back()[1], intervals[i][1]); } } return ans; } }; ``` ### Python ```python # Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution ( object ): def merge ( self , intervals ): """ :type intervals: List[Interval] :rtype: List[Interval] """ ans = [] for intv in sorted ( intervals , key = lambda x : x . start ): if ans and ans [ - 1 ]. end >= intv . start : ans [ - 1 ]. end = max ( ans [ - 1 ]. end , intv . end ) else : ans . append ( intv ) return ans ###### ''' >>> intervals = [[111,222],[1,3],[2,6],[8,10],[15,18]] >>> intervals.sort() >>> intervals [[1, 3], [2, 6], [8, 10], [15, 18], [111, 222]] ''' class Solution : def merge ( self , intervals : List [ List [ int ]]) -> List [ List [ int ]]: intervals . sort () # default sort also ok ans = [ intervals [ 0 ]] for s , e in intervals [ 1 :]: if ans [ - 1 ][ 1 ] < s : ans . append ([ s , e ]) else : ans [ - 1 ][ 1 ] = max ( ans [ - 1 ][ 1 ], e ) return ans ```