LeetCode 56 Merge intervals

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1, 3], [2, 6], [8, 10], [15, 18],
return [1, 6], [8, 10], [15, 18].

Difficulty
Hard

Related Problems
[LeetCode 57] Insert Intervals

Analysis

This problem asks to merge intervals according to their ends' values. Intuitively, we should sort the intervals according to their left ends. After that, we can iterate over the sorted intervals, push the visited interval in vector, merge the following interval if overlapped.

1. Cpp solution

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), 
             [](const Interval &a, const Interval &b){return a.start < b.start;});
        vector<Interval> result;
        if(intervals.size() == 0) return result;
        result.push_back(intervals[0]);

        for(int i = 1; i < (int)intervals.size(); i++){
            if(result.back().end < intervals[i].start){
                result.push_back(intervals[i]);
            }
            else // overlap
                result.back().end = max(result.back().end, intervals[i].end);
        }
        return result;
    }
};

// 2. Go solution

type its []Interval
func (slice its) Len() int {
    return len(slice)
}

func (slice its) Less(i, j int) bool {
    return slice[i].Start < slice[j].Start
}

func (slice its) Swap(i, j int) {
    slice[i], slice[j] = slice[j], slice[i]
}

func merge(intervals []Interval) []Interval {
    res := []Interval{}
    n := len(intervals)
    if n == 0 {
        return res
    }
    ins := its(intervals)
    sort.Sort(ins)

    res = append(res, ins[0])
    for i := 1; i < n; i++ {
        if ins[i].Start <= res[len(res)-1].End {
            res[len(res)-1].End = max(res[len(res)-1].End, ins[i].End)
        } else {
            res = append(res, ins[i])
        }
    }

    return res
}

func max(a, b int) int {
    return int(math.Max(float64(a), float64(b)))
}

Reference