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]
./** * 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 ArrayList<Interval> merge(ArrayList<Interval> intervals) { ArrayList<Interval> res = new ArrayList<Interval>(); if(intervals == null) return intervals; int len = intervals.size(); if(len == 0 || len == 1) return intervals; // sort the input by start value Collections.sort(intervals, new IntervalComparator()); Interval a = intervals.get(0); for(int i = 1; i < len; i++) { Interval b = intervals.get(i); // if mergeable, merge a and b. if(a.end >= b.start) { a = new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end)); } // if not mergeable, move to the next, reset the a node. else { res.add(a); a = b; } } res.add(a); return res; } } class IntervalComparator implements Comparator<interval> { public int compare(Interval a, Interval b) { return a.start - b.start; } }
No comments:
Post a Comment