LeetCode – Merge Intervals
First sort the intervals according to starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i].
1. Sort the intervals based on increasing order of starting time.
2. Push the first interval on to a stack.
3. For each interval do the following
……..a. If the current interval does not overlap with the stack top, push it.
……..b. If the current interval overlaps with stack top and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval.
4. At the end stack contains the merged intervals.
The key to solve this problem is defining a Comparator first to sort the arraylist of Intevals. And then merge some intervals.
The take-away message from this problem is utilizing the advantage of sorted list/array.
http://happycoding2010.blogspot.com/2015/09/leetcode-55-merge-intervals.html
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
public List<Interval> merge(List<Interval> intervals) { Collections.sort(intervals, new Comparator<Interval>(){ @Override public int compare(Interval obj0, Interval obj1) { return obj0.start - obj1.start; } }); List<Interval> ret = new ArrayList<>(); Interval prev = null; for (Interval inter : intervals) { if ( prev==null || inter.start>prev.end ) { ret.add(inter); prev = inter; } else if (inter.end>prev.end) { // Modify the element already in list prev.end = inter.end; } } return ret; }
https://leetcode.com/discuss/24664/fast-ana-simple-java-code
public List<Interval> merge(List<Interval> intervals) { List<Interval> res = new LinkedList<Interval>(); if(intervals.size()<2) return intervals; Collections.sort(intervals, new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { return o1.start-o2.start; } }); Interval curr = intervals.get(0); for(Interval iter: intervals) { if(curr.end >= iter.start) { curr.end = Math.max(curr.end,iter.end); }else { res.add(curr); curr = iter; } } res.add(curr); return res; }
X. https://leetcode.com/discuss/78968/14ms-java-in-place-merge-solution
public List<Interval> merge(List<Interval> intervals) { int N = intervals.size(); Collections.sort(intervals, new Comparator<Interval>(){ public int compare(Interval i, Interval j){ return i.end - j.end; } }); for(int i = N-1; i>0;i--){ Interval inter1 = intervals.get(i-1); Interval inter2 = intervals.get(i); if(inter1.end >= inter2.start){ inter1.start = Math.min(inter1.start, inter2.start); inter1.end = inter2.end; //inter1.end is always smaller than inter2.end because of the sort, so no need to use Math.max() intervals.remove(i); } } return intervals; }
X. https://discuss.leetcode.com/topic/38628/beat-98-java-sort-start-end-respectively
http://www.geeksforgeeks.org/merging-intervals/
Merge intervals in place:
http://www.lifeincode.net/programming/leetcode-merge-intervals-java/
Approach 1: Connected Components
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/056_Merge_Intervals.java
Follow up:
1. followup是如果有⼀一个⾮非常⻓长怎么办
2. 变种:given two sorted arrays of intervals, return the intersection.
ex. a = [(1 5), (8, 10), (15 20)] sorted b = [(2 6), (45 100)] sorted return
[(2, 5)] 我⽤用了了两个pointer指着a和b然后⽤用了了⼏几个case对⽐比 follow up:如何
improve?举了了说很像merge 2 sorted array的问题,说可以⽤用类似⽅方法 然
后就解释了了⼀一⻓长⼀一短两个array的时候可以⽤用遍历短array元素,同时⽤用
binary search 查询⻓长array元素。时间是O(SlogL)的
3. 跟原题不不⼀一样的是他给了了我两个list of intervals 这两个list⾥里里⾯面的
interval都已经各⾃自按照start time sorted了
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Merge%20Two%20Sorted%20Arrays%20of%20Intervals/MergeTwoSortedArraysIntervals.java
2. Two arrays of Intervals merge/intersect
Given a collection of intervals, merge all overlapping intervals.
For example,
Given
return
Given
[1,3],[2,6],[8,10],[15,18]
,return
[1,6],[8,10],[15,18]
.
private class IntervalComparator implements Comparator<Interval> {
@Override
public int compare(Interval a, Interval b) {
return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
}
}
public List<Interval> merge(List<Interval> intervals) {
Collections.sort(intervals, new IntervalComparator());
LinkedList<Interval> merged = new LinkedList<Interval>();
for (Interval interval : intervals) {
// if the list of merged intervals is empty or if the current
// interval does not overlap with the previous, simply append it.
if (merged.isEmpty() || merged.getLast().end < interval.start) {
merged.add(interval);
}
// otherwise, there is overlap, so we merge the current and previous
// intervals.
else {
merged.getLast().end = Math.max(merged.getLast().end, interval.end);
}
}
return merged;
}
First sort the intervals according to starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i].
1. Sort the intervals based on increasing order of starting time.
2. Push the first interval on to a stack.
3. For each interval do the following
……..a. If the current interval does not overlap with the stack top, push it.
……..b. If the current interval overlaps with stack top and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval.
4. At the end stack contains the merged intervals.
The key to solve this problem is defining a Comparator first to sort the arraylist of Intevals. And then merge some intervals.
The take-away message from this problem is utilizing the advantage of sorted list/array.
public ArrayList<Interval> merge(ArrayList<Interval> intervals) { if (intervals == null || intervals.size() <= 1) return intervals; // sort intervals by using self-defined Comparator Collections.sort(intervals, new IntervalComparator()); ArrayList<Interval> result = new ArrayList<Interval>(); Interval prev = intervals.get(0); for (int i = 1; i < intervals.size(); i++) { Interval curr = intervals.get(i); if (prev.end >= curr.start) { // merged case Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end)); prev = merged; // this is better, another way is always compare with latest from list, merge and update it. } else { result.add(prev); prev = curr; } } result.add(prev); return result; } class IntervalComparator implements Comparator<Interval> { public int compare(Interval i1, Interval i2) { return i1.start - i2.start; } }
The key to solve this problem is defining a Comparator first to sort the arraylist of Intevals. And then merge some intervals.
The take-away message from this problem is utilizing the advantage of sorted list/array.
http://blog.csdn.net/linhuanmars/article/details/21857617http://happycoding2010.blogspot.com/2015/09/leetcode-55-merge-intervals.html
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
ArrayList<Interval> res = new ArrayList<Interval>(); if(intervals==null || intervals.size()==0) return intervals; Comparator<Interval> comp = new Comparator<Interval>() { @Override public int compare(Interval i1, Interval i2) { if(i1.start==i2.start) return i1.end-i2.end; return i1.start-i2.start; } }; Collections.sort(intervals,comp); res.add(intervals.get(0)); for(int i=1;i<intervals.size();i++) { if(res.get(res.size()-1).end>=intervals.get(i).start) { res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end, intervals.get(i).end); } else { res.add(intervals.get(i)); } } return res; }https://leetcode.com/articles/merge-intervals/
private class IntervalComparator implements Comparator<Interval> {
@Override
public int compare(Interval a, Interval b) {
return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
}
}
public List<Interval> merge(List<Interval> intervals) {
Collections.sort(intervals, new IntervalComparator());
LinkedList<Interval> merged = new LinkedList<Interval>();
for (Interval interval : intervals) {
// if the list of merged intervals is empty or if the current
// interval does not overlap with the previous, simply append it.
if (merged.isEmpty() || merged.getLast().end < interval.start) {
merged.add(interval);
}
// otherwise, there is overlap, so we merge the current and previous
// intervals.
else {
merged.getLast().end = Math.max(merged.getLast().end, interval.end);
}
}
return merged;
}
https://discuss.leetcode.com/topic/4319/a-simple-java-solution
The idea is to sort the intervals by their starting points. Then, we take the first interval and compare its end with the next intervals starts. As long as they overlap, we update the end to be the max end of the overlapping intervals. Once we find a non overlapping interval, we can add the previous "extended" interval and start over.
Sorting takes O(n log(n)) and merging the intervals takes O(n). So, the resulting algorithm takes O(n log(n)).
public List<Interval> merge(List<Interval> intervals) {
if (intervals.size() <= 1)
return intervals;
// Sort by ascending starting point using an anonymous Comparator
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval i1, Interval i2) {
return Integer.compare(i1.start, i2.start);
}
});
List<Interval> result = new LinkedList<Interval>();
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (Interval interval : intervals) {
if (interval.start <= end) // Overlapping intervals, move the end if needed
end = Math.max(end, interval.end);
else { // Disjoint intervals, add the previous one and reset bounds
result.add(new Interval(start, end));
start = interval.start;
end = interval.end;
}
}
// Add the last interval
result.add(new Interval(start, end));
return result;
}
https://discuss.leetcode.com/topic/12788/a-clean-java-solution/4 public List<Interval> merge(List<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval obj0, Interval obj1) {
return obj0.start - obj1.start;
}
});
List<Interval> ret = new ArrayList<>();
Interval prev = null;
for (Interval inter : intervals) {
if ( prev==null || inter.start>prev.end ) {
ret.add(inter);
prev = inter;
} else if (inter.end>prev.end) {
// Modify the element already in list
prev.end = inter.end;
}
}
return ret;
}
https://leetcode.com/discuss/33434/a-clean-java-solutionpublic List<Interval> merge(List<Interval> intervals) { Collections.sort(intervals, new Comparator<Interval>(){ @Override public int compare(Interval obj0, Interval obj1) { return obj0.start - obj1.start; } }); List<Interval> ret = new ArrayList<>(); Interval prev = null; for (Interval inter : intervals) { if ( prev==null || inter.start>prev.end ) { ret.add(inter); prev = inter; } else if (inter.end>prev.end) { // Modify the element already in list prev.end = inter.end; } } return ret; }
https://leetcode.com/discuss/24664/fast-ana-simple-java-code
public List<Interval> merge(List<Interval> intervals) { List<Interval> res = new LinkedList<Interval>(); if(intervals.size()<2) return intervals; Collections.sort(intervals, new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { return o1.start-o2.start; } }); Interval curr = intervals.get(0); for(Interval iter: intervals) { if(curr.end >= iter.start) { curr.end = Math.max(curr.end,iter.end); }else { res.add(curr); curr = iter; } } res.add(curr); return res; }
X. https://leetcode.com/discuss/78968/14ms-java-in-place-merge-solution
public List<Interval> merge(List<Interval> intervals) { int N = intervals.size(); Collections.sort(intervals, new Comparator<Interval>(){ public int compare(Interval i, Interval j){ return i.end - j.end; } }); for(int i = N-1; i>0;i--){ Interval inter1 = intervals.get(i-1); Interval inter2 = intervals.get(i); if(inter1.end >= inter2.start){ inter1.start = Math.min(inter1.start, inter2.start); inter1.end = inter2.end; //inter1.end is always smaller than inter2.end because of the sort, so no need to use Math.max() intervals.remove(i); } } return intervals; }
X. https://discuss.leetcode.com/topic/38628/beat-98-java-sort-start-end-respectively
http://www.geeksforgeeks.org/merging-intervals/
Merge intervals in place:
void
mergeIntervals(Interval arr[],
int
n)
{
// Sort Intervals in decreasing order of
// start time
sort(arr, arr+n, mycomp);
int
index = 0;
// Stores index of last element
// in output array (modified arr[])
// Traverse all input Intervals
for
(
int
i=0; i<n; i++)
{
// If this is not first Interval and overlaps
// with the previous one
if
(index != 0 && arr[index-1].s <= arr[i].e)
{
// Merge previous and current Intervals
arr[index-1].e = max(arr[index-1].e, arr[i].e);
arr[index-1].s = min(arr[index-1].s, arr[i].s);
}
else
// Doesn't overlap with previous, add to
{
// solution
arr[index] = arr[i];
index++;
}
}
// Now arr[0..index-1] stores the merged Intervals
cout <<
"\n The Merged Intervals are: "
;
for
(
int
i = 0; i < index; i++)
cout <<
"["
<< arr[i].s <<
", "
<< arr[i].e <<
"] "
;
}
void
mergeIntervals(vector<Interval>& intervals)
{
// Test if the given set has at least one interval
if
(intervals.size() <= 0)
return
;
// Create an empty stack of intervals
stack<Interval> s;
// sort the intervals based on start time
sort(intervals.begin(), intervals.end(), compareInterval);
// push the first interval to stack
s.push(intervals[0]);
// Start from the next interval and merge if necessary
for
(
int
i = 1 ; i < intervals.size(); i++)
{
// get interval from stack top
Interval top = s.top();
// if current interval is not overlapping with stack top,
// push it to the stack
if
(top.end < intervals[i].start)
{
s.push( intervals[i] );
}
// Otherwise update the ending time of top if ending of current
// interval is more
else
if
(top.end < intervals[i].end)
{
top.end = intervals[i].end;
s.pop();
s.push(top);
}
}
// Print contents of stack
cout <<
"\n The Merged Intervals are: "
;
while
(!s.empty())
{
Interval t = s.top();
cout <<
"["
<< t.start <<
","
<< t.end <<
"]"
<<
" "
;
s.pop();
}
return
;
}
public List<Interval> merge(List<Interval> intervals) {
List<Interval> ret = new LinkedList<>();
if (intervals.size() == 0)
return ret;
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.start > o2.start)
return 1;
else if (o1.start < o2.start)
return -1;
else {
if (o1.end > o2.end)
return 1;
else if (o1.end < o2.end)
return -1;
}
return 0;
}
});
Interval t = null; // it would be better if we read from 1.
for (Interval interval : intervals) {
if (t == null)
t = interval;
else {
if (t.end >= interval.start) {
t.end = Math.max(t.end, interval.end);
} else {
ret.add(t);
t = interval;
}
}
}
ret.add(t);
return ret;
}
https://leetcode.com/articles/merge-intervals/Approach 1: Connected Components
- Time complexity :Building the graph costs time, as in the worst case all intervals are mutually overlapping. Traversing the graph has the same cost (although it might appear higher at first) because our
visited
set guarantees that each node will be visited exactly once. Finally, because each node is part of exactly one component, the merge step costs time. This all adds up as follows: - Space complexity :As previously mentioned, in the worst case, all intervals are mutually overlapping, so there will be an edge for every pair of intervals. Therefore, the memory footprint is quadratic in the input size.
private Map<Interval, List<Interval>> graph;
private Map<Integer, List<Interval>> nodesInComp;
private Set<Interval> visited;
// return whether two intervals overlap (inclusive)
private boolean overlap(Interval a, Interval b) {
return a.start <= b.end && b.start <= a.end;
}
// build a graph where an undirected edge between intervals u and v exists
// iff u and v overlap.
private void buildGraph(List<Interval> intervals) {
graph = new HashMap<>();
for (Interval interval : intervals) {
graph.put(interval, new LinkedList<>());
}
for (Interval interval1 : intervals) {
for (Interval interval2 : intervals) {
if (overlap(interval1, interval2)) {
graph.get(interval1).add(interval2);
graph.get(interval2).add(interval1);
}
}
}
}
// merges all of the nodes in this connected component into one interval.
private Interval mergeNodes(List<Interval> nodes) {
int minStart = nodes.get(0).start;
for (Interval node : nodes) {
minStart = Math.min(minStart, node.start);
}
int maxEnd = nodes.get(0).end;
for (Interval node : nodes) {
maxEnd = Math.max(maxEnd, node.end);
}
return new Interval(minStart, maxEnd);
}
// use depth-first search to mark all nodes in the same connected component
// with the same integer.
private void markComponentDFS(Interval start, int compNumber) {
Stack<Interval> stack = new Stack<>();
stack.add(start);
while (!stack.isEmpty()) {
Interval node = stack.pop();
if (!visited.contains(node)) {
visited.add(node);
if (nodesInComp.get(compNumber) == null) {
nodesInComp.put(compNumber, new LinkedList<>());
}
nodesInComp.get(compNumber).add(node);
for (Interval child : graph.get(node)) {
stack.add(child);
}
}
}
}
// gets the connected components of the interval overlap graph.
private void buildComponents(List<Interval> intervals) {
nodesInComp = new HashMap();
visited = new HashSet();
int compNumber = 0;
for (Interval interval : intervals) {
if (!visited.contains(interval)) {
markComponentDFS(interval, compNumber);
compNumber++;
}
}
}
public List<Interval> merge(List<Interval> intervals) {
buildGraph(intervals);
buildComponents(intervals);
// for each component, merge all intervals into one interval.
List<Interval> merged = new LinkedList<>();
for (int comp = 0; comp < nodesInComp.size(); comp++) {
merged.add(mergeNodes(nodesInComp.get(comp)));
}
return merged;
}
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/056_Merge_Intervals.java
Follow up:
1. followup是如果有⼀一个⾮非常⻓长怎么办
2. 变种:given two sorted arrays of intervals, return the intersection.
ex. a = [(1 5), (8, 10), (15 20)] sorted b = [(2 6), (45 100)] sorted return
[(2, 5)] 我⽤用了了两个pointer指着a和b然后⽤用了了⼏几个case对⽐比 follow up:如何
improve?举了了说很像merge 2 sorted array的问题,说可以⽤用类似⽅方法 然
后就解释了了⼀一⻓长⼀一短两个array的时候可以⽤用遍历短array元素,同时⽤用
binary search 查询⻓长array元素。时间是O(SlogL)的
3. 跟原题不不⼀一样的是他给了了我两个list of intervals 这两个list⾥里里⾯面的
interval都已经各⾃自按照start time sorted了
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Merge%20Two%20Sorted%20Arrays%20of%20Intervals/MergeTwoSortedArraysIntervals.java
2. Two arrays of Intervals merge/intersect
public List<Interval> merge(List<Interval> a, List<Interval> b) {
int i = 0, j = 0;
Interval last = null;
List<Interval> ans = new ArrayList<>();
while (i < a.size() || j < b.size()) {
// pick the one with less start
Interval cur = null;
if (j == b.size() || (i < a.size() && a.get(i).start < b.get(j).start))
cur = a.get(i ++);
else cur = b.get(j ++);
// merge intervals
if (last == null) {last = cur; continue;}
if (last.end < cur.start) {
ans.add(last);
last = cur;
} else last.end = Math.max(last.end, cur.end);
}
if (last != null) ans.add(last);
return ans;
}
public List<Interval> intersect(List<Interval> a, List<Interval> b) {
int i = 0, j = 0;
List<Interval> ans = new ArrayList<>();
while (i < a.size() && j < b.size()) {
Interval cura = a.get(i);
Interval curb = b.get(j);
if (!(cura.end < curb.start || curb.end < cura.start)) {
Interval inter = new Interval(Math.max(cura.start, curb.start),
Math.min(cura.end, curb.end));
ans.add(inter);
}
if (cura.end < curb.end) i ++;
else j ++;
}
return ans;
}