Array - 56. Merge Intervals

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

思路：

题目意思是合并区间，做法是可以先排序，再遍历区间集合，根据区间首尾来判断是否合并。

代码：

golang：

type myInterval [][]int

func (intervals myInterval)Len() int { return len(intervals) }
func (intervals myInterval)Less(i, j int) bool { return intervals[i][0] < intervals[j][0] } 
func (intervals myInterval)Swap(i, j int) {
    intervals[i], intervals[j] = intervals[j], intervals[i]
}
func (intervals myInterval)back() []int {
    return intervals[len(intervals) - 1]
}
func (intervals *myInterval)pushBack(interval []int) {
    *intervals = append(*intervals, interval)
}
func (intervals *myInterval)modifyBack(i, j int) {
    if i > j {
        (*intervals)[len(*intervals) - 1][1] = i
    } else {
        (*intervals)[len(*intervals) - 1][1] = j
    }
}


func merge(intervals myInterval) [][]int {
    sort.Sort(&intervals)
    
    var res myInterval
    for _, interval := range intervals {
        if len(res) == 0 || interval[0] > res.back()[1] {
            res.pushBack(interval)
        } else {
            // merge
            res.modifyBack(interval[1], res.back()[1])
        }
    }
    
    return res
}


// use sort

import "sort"

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 || len(intervals[0]) == 0 {
        return nil
    }
    
    // sort
    sort.Slice(intervals, func(i, j int) bool{
        return intervals[i][0] < intervals[j][0]
    })
    for k := range intervals {
        sort.Slice(intervals[k], func(i, j int) bool {
            return intervals[k][i] < intervals[k][j]
        })
    }
    
    var res [][]int
    for i := range intervals {
        if len(res) == 0 || res[len(res) - 1][1] < intervals[i][0] {
            res = append(res, intervals[i])
        } else {
            res[len(res) - 1][1] = max(res[len(res) - 1][1], intervals[i][1])
        }
    }
    return res
}

func max(i, j int) int {
    if i < j {
        return j
    }
    return i
}

Java：

class Solution {

    /*public int[][] merge(int[][] intervals) {
        List<int[]> merged = new ArrayList<>();
        if (intervals.length == 0 || intervals == null) return merged.toArray(new int[0][]);
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        int i = 0;
        while (i < intervals.length) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }
            merged.add(new int[]{left, right});
            i++;
        }
        return merged.toArray(new int[0][]);       
    }*/
    
    public int[][] merge(int[][] intervals) {
        int length=intervals.length;
        if(length<=1)
            return intervals;
    
        int[] start = new int[length];
        int[] end = new int[length];
        for(int i=0;i<length;i++){
            start[i]=intervals[i][0];
            end[i]=intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int startIndex=0;
        int endIndex=0;
        List<int[]> result = new LinkedList<>();
        while(endIndex<length){
            //as endIndex==length-1 is evaluated first, start[endIndex+1] will never hit out of index
            if(endIndex==length-1 || start[endIndex+1]>end[endIndex]){
                result.add(new int[]{start[startIndex],end[endIndex]});
                startIndex=endIndex+1;
            }
            endIndex++;
        }
        return result.toArray(new int[result.size()][]);
    }
}