56. Merge Intervals

-
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
---
Clarifying questions
Are time stamps which are exactly the same considered overlapping - example 2
  
Intuition

 Two approaches
1. Event Scan algorithm
2. Merge intervals
---
Event Scan
Event class - capture point, and isStart boolean for each interval point
Sort with custom comparator
if point values are same Boolean.compare(e2.isStart, e1.isStart) -- put Start points first *

When counter becomes zero -- start to current point is merged interval
---
Merge Intervals

Sorting by start time allows to do Left to Right scan and merge overlapping with easy check

Set prev to 1st element

for i in 2... end
if (current start <= prev end)
   merge into prev
else
  add prev to ans
  prev = current

add prev to ans *

---
Time - O(N Log N) - sorting input array
Space - O(1) - not counting output size
---
Related problems
max-meetings-in-room
---
class Solution {
class Event {
int time;
boolean isStart;
public Event(int t, boolean s) {
time = t;
isStart = s;
}
}
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return new int[][] {};
}
List<Event> list = new ArrayList<Event>();
for (int[] interval: intervals) {
list.add(new Event(interval[0], true));
list.add(new Event(interval[1], false));
}
// Keep start before end to accurate identify overlap on same time
Collections.sort(list, (a, b) -> a.time == b.time ? Boolean.compare(b.isStart, a.isStart) : Integer.compare(a.time, b.time));
List<int[]> ret = new ArrayList<int[]>();
for (int i = 0, start = 0, open = 0; i < list.size(); i++) {
if (open == 0) {
start = list.get(i).time;
}
if (list.get(i).isStart) {
open++;
} else {
open--;
}
if (open == 0) {
ret.add(new int[] {start, list.get(i).time});
}
}
int[][] ans = new int[ret.size()][2];
for (int i = 0; i < ret.size(); i++) {
ans[i] = ret.get(i);
}
return ans;
}
}
view raw 56.MergeIntervalsEventScanAlgo.java hosted with ❤ by GitHub
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return new int[][] {};
}
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
int[] prev = intervals[0];
List<int[]> list = new ArrayList<int[]>();
for (int i = 1; i < intervals.length; i++) {
if (prev[1] >= intervals[i][0]) {
prev[1] = Math.max(prev[1], intervals[i][1]);
} else {
list.add(new int[] {prev[0], prev[1]});
prev = intervals[i].clone();
}
}
// make sure to add last entry since the else block isn't executed
list.add(prev);
int[][] ans = new int[list.size()][2];
for (int i = 0; i < list.size(); i++) {
ans[i] = list.get(i);
}
return ans;
}
}
view raw 56.MergeIntervals.java hosted with ❤ by GitHub