[Leetcode] Merge Intevals

Question:

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].

---------------------------------------

Solution:

public class Solution {

    class IntervalAsc implements Comparator<Interval>

      {

        public int compare (Interval o1, Interval o2)

        {

         if (o1.start != o2.start)

            return o1.start < o2.start ? -1 : 1;

          else if (o1.end != o2.end)

            return o1.end < o2.end ? -1 : 1;

          else

            return 0;

      }}

      public ArrayList<Interval> merge (ArrayList<Interval> intervals)

      {

        Collections.sort(intervals, new IntervalAsc());

        ArrayList<Interval> ret = new ArrayList<Interval>();

        int n = intervals.size();

        if(n==0) return ret;

        Interval last=intervals.get(0);

        for(int i=1;i<n;i++){

            if(intervals.get(i).start>last.end){

                ret.add(new Interval(last.start,last.end));

                last=intervals.get(i);

            }else{

                last.end=Math.max(intervals.get(i).end, last.end);

            }

        }

        ret.add(last);

        return ret;

      }

    }

需要注意的以下几点：

这里需要new一个Interval，再放进ArrayList result里。刚开始我就是直接把last放进了result里，忘记了last只是一个类似于指针一样的东西。
第一次使用到了内部类。更多的内部类的知识看下一篇博客。
Collections.sort的用法。（compare函数的重写）

巴特西

[Leetcode] Merge Intevals

最新文章

热门文章