题目描述

原题链接
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

个人解法

Javascript

/*
 * @lc app=leetcode.cn id=56 lang=javascript
 *
 * [56] 合并区间
 */
// @lc code=start
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  const length = intervals.length;
  if (length === 1) {
    return intervals;
  }
  intervals.sort((a, b) => {
    return a[0] - b[0];
  })
  const result = [intervals[0]];
  for (let i = 1; i < length; i++) {
    const len = result.length;
    let index = - 1;
    if (result[len - 1][1] < intervals[i][0]) {
      result.push(intervals[i]);
    }
    else {
      for (let j = len - 1; j >= 0; j--) {
        if (result[j][1] >= intervals[i][0]) {
          index = j;
          break;
        }
      }
      result[index][1] = Math.max(result[index][1], intervals[i][1]);
    }
  }
  return result;
};
// @lc code=end

Java

class Solution {
    public int[][] merge(int[][] intervals) {
        int len= intervals.length,flag=0,f=0;
        int[] temp=new int[]{};
        for (int i=0;i<len-1;i++){
            for (int j=0;j<len-1;j++){
                if (intervals[j][0]>intervals[j+1][0]){
                    temp=intervals[j];
                    intervals[j]=intervals[j+1];
                    intervals[j+1]=temp;
                    flag=1;
                }
            }
            if (flag==1){
                flag=0;
            }else {
                break;
            }
        }
        List<int[]> list=new ArrayList<>();
        int left,right=-1,nowright;
        for (int i=0;i<len-1;i++){
            left=intervals[i][0];
            nowright=intervals[i][1];
            for (int j=i+1;j<len;j++){
                if (intervals[j][0]<=nowright){
                    right=Math.max(intervals[j][1],nowright);
                    nowright=right;
                    flag=j;
                }else {
                    break;
                }
            }
            if (right!=-1){
                int[] nums=new int[]{left,right};
                list.add(nums);
                right=-1;
                i=flag;
                if (i==len-1){
                    f=1;
                }
            }else {
                list.add(intervals[i]);
            }
        }
        if (f==0){
            list.add(intervals[len-1]);
        }
        int size= list.size(),index=0;
        int[][] result=new int[size][];
        for (int[] ints:list){
            result[index++]=ints;
        }
        return result;
    }
}

其他解法

Java

优化之后

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

Javascript