LeetCode challenge – Merge Intervals – Java Solution
This is a solution for the LeetCode challenge – Merge Intervals written in Java ( Source )
Given a collection of intervals, merge all overlapping intervals.
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].
Solution: O(N log N) where N is the number of intervals 1. Sort the intervals based on start index 2. Mark the first interval as the current interval 3. For every ith interval starting 1 -> N, if the ith interval overlaps with the current interval then create a new current interval. Else, add the current interval to result set and begin a new current interval.
Example 1: Input: flowerbed = [1,0,0,0,1], n = 1 Output: True Example 2: Input: flowerbed = [1,0,0,0,1], n = 2 Output: False Note: The input array won’t violate no-adjacent-flowers rule. The input array size is in the range of [1, 20000]. n is a non-negative integer which won’t exceed the input array size.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class MergeIntervals {
public static class Interval {
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
}
public static void main(String[] args) throws Exception {
Interval i1 = new Interval(1, 2);
Interval i2 = new Interval(3, 4);
Interval i3 = new Interval(5, 6);
Interval i4 = new Interval(1, 10);
List<Interval> result = new MergeIntervals().merge(Arrays.asList(i1, i2, i3, i4));
result.forEach((I) -> System.out.println(I.start + " " + I.end));
}
public List<Interval> merge(List<Interval> intervals) {
if (intervals.isEmpty()) return new ArrayList<>();
Collections.sort(intervals, (o1, o2) -> Integer.compare(o1.start, o2.start));
List<Interval> result = new ArrayList<>();
Interval curr = intervals.get(0);
for (int i = 1, l = intervals.size(); i < l; i++) {
Interval I = intervals.get(i);
if (I.start >= curr.start
&& I.start <= curr.end) { // check if the new interval overlaps with the current
curr.end = curr.end > I.end ? curr.end : I.end;
} else {
result.add(curr);
curr = I;
}
}
result.add(curr);
return result;
}
}
