今天下午做了一道题。leetcode merge intervals 属于比较难的题目。
首先用collections.sort 给list排序，然后用两个while loop来比较两个interval 的start， end 。 从而生成新的interal，再插入到新的list 返回结果。
下面给出自己的代码：
/* 50 Merge Intervalshttps://leetcode.com/problems/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; } * } */import java.util.ArrayList;import java.util.List;import java.util.Collections;import java.util.Comparator;public class MergeIntervals {// sort the List, and then compare two Interval in two while loops public static List<Interval> merge(List<Interval> intervals) { // Ref : List<Interval> res = new ArrayList<Interval>(); Collections.sort(intervals, new Comparator<Interval>(){public int compare(Interval p1, Interval p2) {if (p1.start != p2.start )return (p1.start- p2.start );elsereturn (p1.end – p2.end);}});printIntervals(intervals);int i=0;while( i< intervals.size()) {int j= i+1;Interval left = intervals.get(i);int end = left.end;while (j< intervals.size() && end >= intervals.get(j).start) {end = Math.max(end, intervals.get(j).end);j++;}res.add( new Interval(left.start, end));i=j;}// System.out.println("final");// printIntervals(res);return res;}public static void main(String[] args) {Interval interval0 = new Interval(0,2);Interval interval1 = new Interval(4, 6);Interval interval2 = new Interval(1, 1);Interval interval3 = new Interval(5, 5);Interval interval4 = new Interval(3, 3);Interval interval5 = new Interval(5, 6);Interval interval6 = new Interval(0, 1);Interval interval7 = new Interval(0, 1);Interval interval8 = new Interval(1, 2);Interval interval9 = new Interval(5, 6);Interval interval10 = new Interval(5, 5);Interval interval11 = new Interval(0, 0);//[[0,2],[4,6],[1,1],[5,5],[3,3],[5,6],[0,1],[0,1],[1,2],[5,6],[5,5],[0,0]]List<Interval> intervals = new ArrayList<Interval>();intervals.add(interval0);intervals.add(interval1);intervals.add(interval2);intervals.add(interval3);intervals.add(interval4);intervals.add(interval5);intervals.add(interval6);intervals.add(interval7);intervals.add(interval8);intervals.add(interval9);intervals.add(interval10);intervals.add(interval11);//System.out.println(intervals);//Collections.sort(intervals);intervals = merge(intervals);System.out.println("start merge : ");printIntervals(intervals);}public static void printIntervals(List<Interval> intervals) {//System.out.println(intervals);for (int i = 0; i < intervals.size(); i++) {System.out.println("Index: " + i + " – Item: "+ intervals.get(i).start + " "+ intervals.get(i).end);}}}/** * Definition for an interval. */ class Interval {int start;int end;Interval() { start = 0; end = 0; }Interval(int s, int e) { start = s; end = e; }}
，放弃等于又一次可以选择的机会。
