Java-LeetCode56. 合并区间-滑动窗口

• 算法
  • 1.以区间左边界为基准排序区间
  • 2.滑动窗口，start窗口左边界，end窗口右边界
  • 3.往前滑动，当end不在下一个区间之中时，得到一个合并区间停止滑动，移动到下一个区间接着滑动

    // 牛客核心代码
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return new ArrayList<Interval>(10);
        }

        intervals.sort((a, b) -> (a.start - b.start));
        ArrayList<Interval> result = new ArrayList<>(10);
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (int i = 1; i < intervals.size(); i++) {
            if (end < intervals.get(i).start) {
                result.add(new Interval(start, end));
                start = intervals.get(i).start;
            }
            end = Math.max(end, intervals.get(i).end);
        }
        result.add(new Interval(start, end));
        return result;
    }

// LeetCode核心代码
public int[][] merge(int[][] intervals) {
    if (intervals == null || intervals.length == 0) {
        return new int[0][2];
    }

    Arrays.sort(intervals, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
    ArrayList<int[]> list = new ArrayList<>(10);
    int start = intervals[0][0];
    int end = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
        if (end < intervals[i][0]) {
            list.add(new int[]{start, end});
            start = intervals[i][0];
        }
        end = Math.max(end, intervals[i][1]);
    }
    list.add(new int[]{start, end});
    int[][] result = new int[list.size()][];
    for (int i = 0; i < list.size(); i++) {
        result[i] = list.get(i);
    }
    return result;
}