首页 > 代码库 > 【leetcode刷题笔记】Merge Intervals
【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]
.
题解:首先对所有的区间按照start大小排序,然后遍历排序后的数组,用last记录前一个区间,如果遍历的当前区间可以和last合并,就把它合并到last里面;否则就把last放到answer list中,并且更新last。
代码如下:
1 /** 2 * Definition for an interval. 3 * public class Interval { 4 * int start; 5 * int end; 6 * Interval() { start = 0; end = 0; } 7 * Interval(int s, int e) { start = s; end = e; } 8 * } 9 */10 public class Solution {11 class IntervalComparator implements Comparator<Interval>{12 public int compare(Interval a,Interval b){13 return a.start - b.start;14 }15 }16 public List<Interval> merge(List<Interval> intervals) {17 if(intervals == null || intervals.size() <= 1)18 return intervals;19 Collections.sort(intervals,new IntervalComparator());20 21 ArrayList<Interval> answer = new ArrayList<Interval>();22 23 Interval last = intervals.get(0);24 for(int i = 1;i < intervals.size();i++){25 Interval now = intervals.get(i);26 if(last.end >= now.start){27 last.end = Math.max(last.end, now.end);28 }29 else{30 answer.add(last);31 last = now;32 }33 }34 answer.add(last);35 return answer;36 37 38 }39 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。