Intervals
Merge Intervals
DESCRIPTION (inspired by Leetcode.com)
Write a function to consolidate overlapping intervals within a given array intervals, where each interval intervals[i] consists of a start time starti and an end time endi.
Two intervals are considered overlapping if they share any common time, including if one ends exactly when another begins (e.g., [1,4] and [4,5] overlap and should be merged into [1,5]).
The function should return an array of the merged intervals so that no two intervals overlap and all the intervals collectively cover all the time ranges in the original input.
Input:
intervals = [[3,5],[1,4],[7,9],[6,8]]
Output:
[[1,5],[6,9]]
Explanation: The intervals [3,5] and [1,4] overlap and are merged into [1,5]. Similarly, [7,9] and [6,8] overlap and are merged into [6,9].
public class Solution {
public int[][] mergeIntervals(int[][] intervals) {
// Your code goes here
}
}Run your code to see results here
Have suggestions or found something wrong?
Explanation
Since this question involves merging intervals that overlap, we want to first sort the intervals by their start time. This allows us to easily check if an interval overlaps with the one before it. Then we create a new array to store the merged intervals.
We iterate through the sorted intervals and check if the current interval overlaps with the last interval in the merged array. If it does, we merge the intervals by updating the end time of the last interval in the merged array to be the maximum of the end times of the current interval and the last interval in the merged array (i.e. max(merged[-1][1], current[1])).
Note the first interval can always be added directly to the merged array.
public int[][] mergeIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> merged = new ArrayList<>();for (int[] interval : intervals) {if (merged.isEmpty() || interval[0] > merged.get(merged.size() - 1)[1]) {merged.add(interval);} else {merged.get(merged.size() - 1)[1] = Math.max(interval[1], merged.get(merged.size() - 1)[1]);}}return merged.toArray(new int[merged.size()][]);}
intervals[1]
0 / 1
If it doesn't, we add the current interval directly to the merged array.
public int[][] mergeIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> merged = new ArrayList<>();for (int[] interval : intervals) {if (merged.isEmpty() || interval[0] > merged.get(merged.size() - 1)[1]) {merged.add(interval);} else {merged.get(merged.size() - 1)[1] = Math.max(interval[1], merged.get(merged.size() - 1)[1]);}}return merged.toArray(new int[merged.size()][]);}
intervals[2]
0 / 1
What is the time complexity of this solution?
O(V + E)
O(n)
O(n³)
O(n * logn)
Solution
public int[][] mergeIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> merged = new ArrayList<>();for (int[] interval : intervals) {if (merged.isEmpty() || interval[0] > merged.get(merged.size() - 1)[1]) {merged.add(interval);} else {merged.get(merged.size() - 1)[1] = Math.max(interval[1], merged.get(merged.size() - 1)[1]);}}return merged.toArray(new int[merged.size()][]);}
merge intervals
0 / 10