[leetcode] Merge Intervals
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].
https://oj.leetcode.com/problems/merge-intervals/
考え方:まず開始点に従ってソートし、次にマージを巡回します.
コード:
参照先:
http://leetcodenotes.wordpress.com/2013/08/01/merge-intervals/
For example, Given[1,3],[2,6],[8,10],[15,18], return[1,6],[8,10],[15,18].
https://oj.leetcode.com/problems/merge-intervals/
考え方:まず開始点に従ってソートし、次にマージを巡回します.
コード:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if (intervals == null)
return null;
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
ArrayList<Interval> res = new ArrayList<Interval>();
int i;
for (i = 0; i < intervals.size();) {
int j = i + 1;
Interval merged = new Interval(intervals.get(i).start,
intervals.get(i).end);
while (j < intervals.size()
&& isConnected(merged, intervals.get(j))) {
merged = merge(merged, intervals.get(j));
j++;
}
res.add(merged);
i = j;
}
return res;
}
private boolean isConnected(Interval a, Interval b) {
return (a.start >= b.start && a.start <= b.end)
|| (b.start >= a.start && b.start <= a.end);
}
private Interval merge(Interval a, Interval b) {
int newStart = a.start < b.start ? a.start : b.start;
int newEnd = a.end > b.end ? a.end : b.end;
a.start = newStart;
a.end = newEnd;
return a;
}
public static void main(String[] args) {
// [1,3],[2,6],[8,10],[15,18]
Interval one = new Interval(2, 4);
Interval two = new Interval(1, 2);
Interval three = new Interval(4, 10);
Interval four = new Interval(10, 18);
ArrayList<Interval> intervals = new ArrayList<Interval>();
intervals.add(one);
intervals.add(two);
intervals.add(three);
intervals.add(four);
System.out.println(new Solution().merge(intervals));
}
}
参照先:
http://leetcodenotes.wordpress.com/2013/08/01/merge-intervals/