Merge Intervals
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]
./** * 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; } * } */
import java.util.Collections; public class Solution { public ArrayList<Interval> merge(ArrayList<Interval> intervals) { // Start typing your Java solution below // DO NOT write main() function Collections.sort(intervals, new Comparator<Interval>(){public int compare(Interval a, Interval b){return a.start>b.start?1:(a.start==b.start?0:-1);}}); ArrayList<Interval> res = new ArrayList<Interval>(); int i=0; while(i<intervals.size()){ int j=i+1; int end = intervals.get(i).end; while(j<intervals.size() && end>=intervals.get(j).start){ end=Math.max(end, intervals.get(j).end); j++; } res.add(new Interval(intervals.get(i).start,end)); i=j; } return res; } }
No comments:
Post a Comment