If you want to master array problems, “Merge Intervals” is a must-know question! In this blog, we\u2019ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Given an array of Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Example 1:<\/strong><\/p>\n\n\n\n Example 2:<\/strong><\/p>\n\n\n\n Constraints:<\/strong><\/p>\n\n\n\n Let\u2019s solve the problem step by step in the simplest way:<\/p>\n\n\n\nintervals<\/code> where intervals[i] = [starti<\/sub>, endi<\/sub>]<\/code>, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input<\/em>.<\/p>\n\n\n\nInput:<\/strong> intervals = [[1,3],[2,6],[8,10],[15,18]]
Output:<\/strong> [[1,6],[8,10],[15,18]]
Explanation:<\/strong> Since intervals [1,3] and [2,6] overlap, merge them into [1,6].<\/pre>\n\n\n\nInput:<\/strong> intervals = [[1,4],[4,5]]
Output:<\/strong> [[1,5]]
Explanation:<\/strong> Intervals [1,4] and [4,5] are considered overlapping.<\/pre>\n\n\n\n\n
1 <= intervals.length <= 104<\/sup><\/code><\/li>\n\n\n\nintervals[i].length == 2<\/code><\/li>\n\n\n\n0 <= starti<\/sub> <= endi<\/sub> <= 104<\/sup><\/code><\/li>\n<\/ul>\n\n\n
\n\n\n\nBrute Force Solution<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Sorting helps us line up all intervals so that overlapping intervals are next to each other.<\/li>\n\n\n\n
For every interval, try to merge it with all future intervals that overlap with it.<\/li>\n\n\n\n
If an interval is already covered by a previous merge, skip it.<\/li>\n\n\n\n
We check every possible overlap and merge accordingly. This ensures all intervals are merged correctly, but it\u2019s not the most efficient.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n