Given an array of intervals where each interval is represented by a pair of integers indicating its start and end points. Write a program to merge all overlapping intervals and return a new array containing strictly non-overlapping intervals that cover the exact same total span of values. The input array is not guaranteed to be sorted initially.
Example 1
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: The intervals [1, 3] and [2, 6] overlap with each other because the second interval begins before the first one concludes. They are safely consolidated into a single continuous block from 1 to 6. The remaining intervals do not clash and are left untouched.
Example 2
Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: The interval [1, 4] ends at the exact same point that [4, 5] begins. Because they share a boundary, they are considered overlapping and are merged into a single span from 1 to 5.
Brute Force Approach
The direct idea is to sort intervals by start time, then start from each interval and look ahead to absorb every following interval that overlaps with it. The merged range begins with the current interval's start and grows while later intervals start before or exactly at the current merged end.
If an interval is already covered by the last merged range, it can be skipped. This avoids adding the same merged span again. The method is still less direct because it searches ahead from each new merge start instead of maintaining one active range throughout the scan.
Algorithm
Return the input directly when it contains
0or1interval.Sort all intervals by their start time.
Create an empty result list to store merged intervals.
For each interval, skip it if its end is already covered by the last interval in the result.
Otherwise, use it as the start of a new merged range and look ahead while following intervals overlap.
Add the final merged range to the result and return the result after all intervals are checked.
Dry Run
Merge Intervals
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns all intervals after merging overlaps with look-ahead scanning. vector<vector<int>> mergeBrute(vector<vector<int>>& intervals) { int n = intervals.size(); // A list with at most one interval is already merged. if (n <= 1) { return intervals; } // Sort intervals by start time so possible overlaps become adjacent. sort(intervals.begin(), intervals.end()); vector<vector<int>> result; // Try to build one merged interval starting from each position. for (int i = 0; i < n; i++) { // A covered interval is already part of the last merged range. if (!result.empty() && intervals[i][1] <= result.back()[1]) { continue; } int start = intervals[i][0]; int end = intervals[i][1]; // Look ahead and absorb every interval that overlaps the current range. for (int j = i + 1; j < n; j++) { // Overlap means the current merged range may need a larger end. if (intervals[j][0] <= end) { end = max(end, intervals[j][1]); // A later start beyond the current end means the merge range is complete. } else { break; } } result.push_back({start, end}); } return result; }};// Driver codeint main() { vector<vector<int>> intervals = {{8, 10}, {1, 3}, {2, 6}, {15, 18}, {17, 20}, {10, 12}, {7, 9}}; // instance for class Solution Solution sol; vector<vector<int>> result = sol.mergeBrute(intervals); // Print every merged interval. for (vector<int>& interval : result) { cout << '[' << interval[0] << ", " << interval[1] << "] "; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N log N + N2). Sorting the array requires O(N log N) operations. In the worst-case scenario where intervals are structured to cause maximum redundant scans, the nested loops will look ahead across elements quadratically, dominating the final runtime.
Space Complexity: O(N). We must allocate auxiliary memory for a brand new array structure to hold our final consolidated outputs.
Optimal Approach
After sorting by start time, overlapping intervals appear next to each other. This means a single active merged interval is enough.
If the next interval starts after the end of the last merged interval, it cannot overlap and should begin a new range. Otherwise, it overlaps with the last merged interval, so only the end of that last interval needs to be extended.
This avoids repeatedly looking ahead from each interval. Each interval is handled once after sorting.
Algorithm
Return the input directly when it contains
0or1interval.Sort all intervals by their start time.
Create an empty result list.
Traverse intervals from left to right.
Append the current interval when the result is empty or when it starts after the last merged interval ends.
Otherwise, merge it by extending the last merged interval's end, then return the result.
Dry Run
Merge Intervals
Solution
// C++ program to merge intervals using Linear Single Pass optimal approach#include <bits/stdc++.h>using namespace std;class Solution {public: vector<vector<int>> mergeOptimal(vector<vector<int>>& intervals) { int n = intervals.size(); if (n <= 1) return intervals; // Sort intervals based on start times sort(intervals.begin(), intervals.end()); vector<vector<int>> result; for (int i = 0; i < n; i++) { // If result is empty or current interval does not overlap with the last one if (result.empty() || result.back()[1] < intervals[i][0]) { result.push_back(intervals[i]); } // If there is an overlap, merge by updating the end time of the last interval else { result.back()[1] = max(result.back()[1], intervals[i][1]); } } return result; }};int main() { Solution sol; vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}}; vector<vector<int>> result = sol.mergeOptimal(intervals); cout << "Merged intervals: "; for (int i = 0; i < result.size(); i++) { cout << "[" << result[i][0] << ", " << result[i][1] << "] "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N log N). Sorting the array requires O(N log N) operations. The subsequent array traversal loop visits every single item exactly once, executing in strictly linear O(N) time, which makes sorting the absolute bottleneck.
Space Complexity: O(N). Auxiliary memory is allocated to build and safely hold the final merged result array before returning it to the caller.
Interview follow-up Questions
If the array is unsorted, overlapping intervals can be scattered anywhere across the dataset. For instance, [1, 5] could be at index 0, and [2, 3] could be buried at the very end of a massive array. Sorting forces all intervals to align chronologically based on their starting boundaries, ensuring that overlapping blocks are mathematically guaranteed to sit next to each other.
Be the first to add a comment.