数组-区间合并

一、题目描述

二、题目思路

这里提供满足基本要求的解题思路：

1.先对列表内按照start大小升序排序，这里创建Comparator接口的实现类，重写compare方法。

2.遍历intervals，设置laststart、lastend两个变量与当前区间相比较，合并公共空间，注意存在区间A包含区间B的情况。

3.在遍历完成后，还要注意把 [laststart,lastend] 区间加到返回列表中。

三、代码实现

import java.util.*;
/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

class CompareImpl implements Comparator<Interval> {

    //重写比较方法，按照Interval.start排序，如果相等按照end排序
    @Override
    public int compare(Interval inter1, Interval inter2) {
        if (inter1.start < inter2.start) {
            return -1;
        } else if (inter1.start == inter2.start) {
            if (inter1.end <= inter2.end) {
                return -1;
            } else {
                return 1;
            }
        } else {
            return 1;
        }
    }

}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类ArrayList
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        // write code here
        if (intervals.size() <= 1) {
            return intervals;
        }
        //首先对intervals进行排序
        intervals.sort(new CompareImpl());

        //遍历intervals，合并公共空间
        ArrayList<Interval> resarr = new ArrayList<>(0);
        Iterator<Interval> intiv = intervals.iterator();
        int laststart = -1, lastend = -1;

        while (intiv.hasNext()) {
            Interval nowinterval = intiv.next();
            if (laststart == -1) { //当前集合不需要合并操作时
                laststart = nowinterval.start;
                lastend = nowinterval.end;
            } else {
                if (lastend >= nowinterval.start) {
                    //这里合并时，除了 [[1,2],[2,3]] 还要注意测试用例 [[1,4],[2,3]] 的情况
                    lastend=lastend<nowinterval.end?nowinterval.end:lastend;
                } else {
                    Interval newinterval = new Interval(laststart, lastend);
                    resarr.add(newinterval);

                    //更新laststart和lastend
                    laststart=nowinterval.start;
                    lastend=nowinterval.end;
                }
            }
        }
        //最后还需要把laststart和lastend区间加入到resarr中
        Interval newinterval = new Interval(laststart, lastend);
        resarr.add(newinterval);

        return resarr;
    }
}