【LeetCode】Merge Intervals
1801 ワード
テーマ
Given a collection of intervals、merge all overlapping intervals.
For example,Given
答えを出す
まず間隔を起点にして小さいものから大きいものに並べ替えます。(起点は同じ終点です。)では、問題は来ました。どうやって対象を並べ替えますか?
Javaは自分の並べ替えとコンパレータを集合することによって実現することができます。すなわち、java.util.Coollections.sort(List,Comprator)。
並べ替え後、最初の区間を統合した後のListを、マージ後のListの最後の区間の終点とintervalsの最初の起点と比較して、判断するかどうか
合併、合併はListの最後の間隔の終点を修正し、合併しないで直接add Listに進み、循環はintervalsを経由すればいいです。コードは以下の通りです。
Given a collection of intervals、merge all overlapping intervals.
For example,Given
[1,3],[2,6],[8,10],[15,18]
、リセット [1,6],[8,10],[15,18]
.答えを出す
まず間隔を起点にして小さいものから大きいものに並べ替えます。(起点は同じ終点です。)では、問題は来ました。どうやって対象を並べ替えますか?
Javaは自分の並べ替えとコンパレータを集合することによって実現することができます。すなわち、java.util.Coollections.sort(List,Comprator)。
並べ替え後、最初の区間を統合した後のListを、マージ後のListの最後の区間の終点とintervalsの最初の起点と比較して、判断するかどうか
合併、合併はListの最後の間隔の終点を修正し、合併しないで直接add Listに進み、循環はintervalsを経由すればいいです。コードは以下の通りです。
/**
* 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) {
List<Interval> list=new ArrayList<Interval>();
if(intervals==null||intervals.size()==0){ // intervals , 0
return intervals; // intervals, null, [], []
}
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);
list.add(intervals.get(0));
for(int i=1;i<intervals.size();i++){
if(list.get(list.size()-1).end>=intervals.get(i).start){
list.get(list.size()-1).end=Math.max(list.get(list.size()-1).end,intervals.get(i).end); // end
}else{
list.add(intervals.get(i));
}
}
return list;
}
}
---EOF---