Question
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].
Stats
| Frequency | 5 |
| Difficulty | 4 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Solution
The idea of the solution is not difficult. First, sort the entire collection list by start time. Secondly, merge it.
The real difficult part is how to sort the collection.
We can of course do insertion sort, or binary insertion sort. However, from this article:
The straight insertion algorithm presented in the preceding section does a linear search to find the position in which to do the insertion. However, since the element is inserted into a sequence that is already sorted, we can use a binary search instead of a linear search. Whereas a linear search requires O(n) comparisons in the worst case, a binary search only requires O(logn) comparisons. Therefore, if the cost of a comparison is significant, the binary search may be preferred.
And from wikipedia:
If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2(n)⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n^2) on average because of the series of swaps required for each insertion.
So insertion sort algorithm may not be the best choice for us!
A more popular solution is using Collection.sort function.
java.util.Collections
public static
void sort(List list, Comparator<? super T> c) Parameters: c
The comparator to determine the order of the list. A null value indicates that the elements’ natural ordering should be used.
A new class that implements the Comparator interface is created, and inside there is compare(Interval, Interval) method. Here is one example of such solution.
The third solution is same as the second, but only different in implementing the comparator object. Note the following code from this blog:
Comparator
public int compare(Interval i1, Interval i2){
Integer i1St=i1.start;
Integer i2St=i2.start;
return i1St.compareTo(i2St);
}
};
Read 3 pieces of code below.
My code
insertion sort, then merge:
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
ArrayList<Interval> ans = new ArrayList<Interval>();
int len = intervals.size();
if (len == 0) return ans;
ans.add(intervals.get(0));
if (len == 1) return ans;
// now intervals length is >= then 2
if (intervals.get(0).start < intervals.get(1).start)
ans.add(intervals.get(1));
else ans.add(0, intervals.get(1));
for (int i = 2; i < len; i++) {
int cur = intervals.get(i).start;
// now find number cur from ans<list>
int left = 0, right = ans.size() - 1;
while (right - left > 1) {
int mid = (left + right) / 2;
if (ans.get(mid).start < cur) left = mid;
else right = mid;
}
// insert cur between left and right, unless:
if (left == 0 && cur < ans.get(0).start)
ans.add(0, intervals.get(i));
else if (right == ans.size() - 1
&& cur > ans.get(ans.size() - 1).start)
ans.add(intervals.get(i));
else
ans.add(right, intervals.get(i));
}
// now merge ans
int k = 0;
while (k < ans.size() - 1) {
while (k < ans.size() - 1 && ans.get(k).end >= ans.get(k + 1).start) {
ans.get(k).end = Math.max(ans.get(k).end, ans.get(k + 1).end);
ans.remove(k + 1);
}
k++;
}
return ans;
}
Recommended solution. Creating a new Comparator class
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() == 0) {
return intervals;
}
Collections.sort(intervals, new IntervalComparator());
int p = 0;
// if p is the last element of the list, we should stop merging
while (p < intervals.size() - 1) {
// merge p with the next interval, if possible
if (intervals.get(p).end >= intervals.get(p + 1).start) {
intervals.get(p).end = Math.max(intervals.get(p).end, intervals.get(p + 1).end);
intervals.remove(p + 1);
} else {
p++;
}
}
return intervals;
}
class IntervalComparator implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}
}
Third solution, different way of writing Comparator.
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if (intervals == null || intervals.size() < 2)
return intervals;
ArrayList<Interval> result = new ArrayList<Interval>();
Comparator<Interval> intervalComperator = new Comparator<Interval>() {
public int compare(Interval i1, Interval i2) {
Integer i1St = i1.start;
Integer i2St = i2.start;
return i1St.compareTo(i2St);
}
};
Collections.sort(intervals, intervalComperator);
Interval current = intervals.get(0);
int i = 1;
while (i < intervals.size()) {
Interval currentToCompare = intervals.get(i);
if (current.end < currentToCompare.start) {
result.add(current);
current = currentToCompare;
} else
current.end = Math.max(current.end, currentToCompare.end);
i++;
}
result.add(current);
return result;
}