Easy Java Solution.beats 95%


  • 0
    X
    /**
     * 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; }
     * }
     */
    class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            //给定数组对,合并所有重叠的数组对,返回其合并的结果。
            //思路:类似Calendar时间安排,只需要使用List集合,用count记录已经存储的对数。每次完成新的匹配,则需要更新整个队列 
            
            //注意:每次生成新的数组对,判断是否对其他数组对有影响,直到整个数组对没有影响为止
            List <Interval> list = new ArrayList <>();
            if (intervals.size() == 0 || intervals.isEmpty()) return list;
            for (Interval in : intervals) {
                //标志位
                int i = 0;
                for (i = 0; i < list.size()&&!list.isEmpty(); i++) {
                    //判断该元素跨了几个区间
    
                    //判断是否存在交集
                    if (list.get(i).start > in.end) {
                        list.add(i,in);
                        break;
                    } else if (list.get(i).end < in.start) {
                        //..
                        continue;
                    } else {
                        //存在交集
                        if (list.get(i).start < in.start) {
                            in.start = list.get(i).start;
                        }
                        if (list.get(i).end > in.end) {
                            in.end = list.get(i).end;
                        }
                        //移除该元素
                        list.remove(i);
                        i--;
                    }
                }
                if (i == list.size() || list.size() == 0) {
                    list.add(in);
                }
                
            }
            return list;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.