BM89 题解 | #合并区间#
合并区间
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a
看见进步: Good job!
这道题本来是感觉自己做不出来的,应该不行的,突然,画了一下图,就是一个区间排序,就跟游戏一样,有重合的判断,不就可以了吗?之后就自己做出来了。
还有跟值得骄傲自豪的是,我居然把快排也实现了,没有用系统的快排方法,太牛逼了!
解题思路:
1、给区间排序,
2、判断区间重合,若是合并,删除上一个加入新的,若否,直接添加
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param intervals Interval类ArrayList * @return Interval类ArrayList */ public ArrayList<Interval> merge (ArrayList<Interval> intervals) { ArrayList<Interval> res = new ArrayList<Interval>(); if(intervals == null || intervals.size()==0) { return res; } // List<Interval> sorts = quickSort(intervals); Collections.sort(intervals, new Comparator<Interval>(){ public int compare(Interval o1, Interval o2) { if(o1.start != o2.start) return o1.start - o2.start; else return o1.end - o2.end; } }); int size = intervals.size(); res.add(intervals.get(0)); for(int i=1; i<size; i++) { Interval i1 = res.get(res.size()-1); Interval i2 = intervals.get(i); if(isIntervalContain(i1, i2)){ res.remove(res.size()-1); res.add(mergeInterval(i1, i2)); } else { res.add(i2); } } return res; } boolean isIntervalContain(Interval i1, Interval i2) { if(i2.start <= i1.end) { return true; } return false; } Interval mergeInterval(Interval i1, Interval i2) { int start = i1.start <= i2.start ? i1.start: i2.start; int end = i1.end <= i2.end ? i2.end : i1.end; return new Interval(start, end); } /** * 我自己写的快排算法 */ List<Interval> quickSort(List<Interval> datas) { if(datas==null || datas.size()==1) { return datas; } int low = 0; int high = datas.size(); int mid = (high - low)/2; List<Interval> leftDatas = datas.subList(low, mid); List<Interval> rightDatas = datas.subList(mid, high); return merge(quickSort(leftDatas), quickSort(rightDatas)); } ArrayList<Interval> merge(List<Interval> d1, List<Interval> d2) { ArrayList<Interval> res = new ArrayList<Interval>(); int i1 = 0, i2 = 0; while(i1< d1.size() && i2<d2.size()) { Interval iv1 = d1.get(i1); Interval iv2 = d2.get(i2); if(iv1.start < iv2.start) { res.add(iv1); i1++; } else { res.add(iv2); i2++; } } while(i1 < d1.size()) { res.add(d1.get(i1)); i1++; } while(i2 < d2.size()) { res.add(d2.get(i2)); i2++; } return res; } }