Description:
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.
Examples:
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.Solution in Python:
Python
from typing import List
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# First, sort the intervals based on the starting times.
intervals.sort(key=lambda x: x[0])
# Initialize an empty list to store the merged intervals.
merged_intervals = []
# Iterate through each interval in the sorted list.
for interval in intervals:
# If merged_intervals is empty or the current interval does not overlap with the previous one,
# simply add it to merged_intervals.
if not merged_intervals or merged_intervals[-1][1] < interval[0]:
merged_intervals.append(interval)
else:
# If there is an overlap, merge the current interval with the last interval in merged_intervals.
# Update the end of the last interval to be the maximum end of both intervals.
merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1])
# Return the list of merged intervals.
return merged_intervalsExplanation of the Code:
- Sorting the Intervals:
- The first step is to sort the intervals based on their starting times. This helps in easily identifying overlaps as we iterate through the sorted list.
- We use
intervals.sort(key=lambda x: x[0])to sort the intervals based on the first element of each interval (i.e., the start time).
- Initializing the Merged Intervals List:
merged_intervalsis an empty list that will eventually contain all the merged intervals.
- Iterating Through the Sorted Intervals:
- We iterate through each interval in the sorted list of intervals.
- For each interval, we check if
merged_intervalsis empty or if the current interval does not overlap with the last interval inmerged_intervals. - If there is no overlap (i.e., the end of the last interval in
merged_intervalsis less than the start of the current interval), we simply append the current interval tomerged_intervals.
- Merging Overlapping Intervals:
- If there is an overlap (i.e., the end of the last interval in
merged_intervalsis greater than or equal to the start of the current interval), we merge the intervals. - This is done by updating the end of the last interval in
merged_intervalsto be the maximum end time of the current interval and the last interval inmerged_intervals.
- If there is an overlap (i.e., the end of the last interval in
- Returning the Result:
- Finally, we return the
merged_intervalslist which now contains all the non-overlapping intervals after merging the overlapping ones.
- Finally, we return the
This approach ensures that all intervals are considered and merged efficiently, resulting in a time complexity of O(n log n) due to the initial sort and O(n) for the merge process, where n is the number of intervals.
Solution in Javascript:
JavaScript
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
// First, sort the intervals based on the starting times.
intervals.sort((a, b) => a[0] - b[0]);
// Initialize an empty array to store the merged intervals.
const mergedIntervals = [];
// Iterate through each interval in the sorted list.
for (let interval of intervals) {
// If mergedIntervals is empty or the current interval does not overlap with the previous one,
// simply add it to mergedIntervals.
if (mergedIntervals.length === 0 || mergedIntervals[mergedIntervals.length - 1][1] < interval[0]) {
mergedIntervals.push(interval);
} else {
// If there is an overlap, merge the current interval with the last interval in mergedIntervals.
// Update the end of the last interval to be the maximum end of both intervals.
mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]);
}
}
// Return the array of merged intervals.
return mergedIntervals;
};Solution in Java:
Java
import java.util.Arrays;
import java.util.ArrayList;
class Solution {
public int[][] merge(int[][] intervals) {
// First, sort the intervals based on the starting times.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// Initialize an ArrayList to store the merged intervals.
ArrayList<int[]> mergedIntervals = new ArrayList<>();
// Iterate through each interval in the sorted list.
for (int[] interval : intervals) {
// If mergedIntervals is empty or the current interval does not overlap with the previous one,
// simply add it to mergedIntervals.
if (mergedIntervals.size() == 0 || mergedIntervals.get(mergedIntervals.size() - 1)[1] < interval[0]) {
mergedIntervals.add(interval);
} else {
// If there is an overlap, merge the current interval with the last interval in mergedIntervals.
// Update the end of the last interval to be the maximum end of both intervals.
mergedIntervals.get(mergedIntervals.size() - 1)[1] =
Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]);
}
}
// Convert the ArrayList to a 2D array and return it.
return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public int[][] Merge(int[][] intervals) {
// First, sort the intervals based on the starting times.
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
// Initialize a list to store the merged intervals.
List<int[]> mergedIntervals = new List<int[]>();
// Iterate through each interval in the sorted list.
foreach (var interval in intervals) {
// If mergedIntervals is empty or the current interval does not overlap with the previous one,
// simply add it to mergedIntervals.
if (mergedIntervals.Count == 0 || mergedIntervals[mergedIntervals.Count - 1][1] < interval[0]) {
mergedIntervals.Add(interval);
} else {
// If there is an overlap, merge the current interval with the last interval in mergedIntervals.
// Update the end of the last interval to be the maximum end of both intervals.
mergedIntervals[mergedIntervals.Count - 1][1] =
Math.Max(mergedIntervals[mergedIntervals.Count - 1][1], interval[1]);
}
}
// Convert the list to a 2D array and return it.
return mergedIntervals.ToArray();
}
}