708874. Overlapping Intervals
Overlapping Intervals
Slug: overlapping-intervals--170633
Difficulty: Medium
Id: 708874
Topic Tags: Arrays, Hash, Sorting, Data Structures, Algorithms
Company Tags: Amazon, Microsoft, Google, Nutanix, Zoho
Summary
Given an array of intervals where each interval is represented as a pair of integers (start, end), write a program to find all overlapping intervals. For example, given the following intervals:
| Start | End | | --- | --- | | 1 | 3 | | 2 | 4 | | 5 | 7 | | 6 | 8 |
The output should be:
| Start | End | | --- | --- | | 1 | 3 | | 2 | 4 | | 5 | 8 |
Detailed Explanation
To solve this problem, we can sort the intervals based on their start time. Then, iterate through the sorted intervals and keep track of the current interval's end time. If a new interval starts within the range of the current interval, it means they overlap, so update the current interval's end time to be the maximum of the two.
Here is a step-by-step breakdown of the solution:
- Sort the intervals based on their start time.
- Initialize an empty list to store the overlapping intervals.
- Iterate through the sorted intervals:
- If the current interval starts within the range of the previous interval (i.e.,
prev_end >= curr_start), it means they overlap, so update the previous interval's end time to be the maximum of the two (prev_end = max(prev_end, curr_end)). - Otherwise, add the current interval to the list and set the previous interval to the current one.
- If the current interval starts within the range of the previous interval (i.e.,
- Return the list of overlapping intervals.
Time complexity: O(n log n) due to sorting Space complexity: O(n) for storing the overlapping intervals
Optimized Solutions
Java
import java.util.ArrayList;
import java.util.List;
public class OverlappingIntervals {
public static List<int[]> findOverlapping(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();
int prevStart = intervals[0][0];
int prevEnd = intervals[0][1];
for (int[] interval : intervals) {
if (interval[0] <= prevEnd) {
prevEnd = Math.max(prevEnd, interval[1]);
} else {
result.add(new int[] {prevStart, prevEnd});
prevStart = interval[0];
prevEnd = interval[1];
}
}
result.add(new int[] {prevStart, prevEnd});
return result;
}
}