Merge Intervals Leetcode


#1

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].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

#2
  1. Sort the intervals by start time.
  2. Process and find out intervals that can be merged.
/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */

 type IntervalStartSort []Interval
 func (is IntervalStartSort) Len() int { return len(is)}
 func (is IntervalStartSort) Swap(i, j int){ is[i], is[j] = is[j], is[i] }
 func (is IntervalStartSort) Less(i, j int) bool { return is[i].Start < is[j].Start}
 
 func merge(intervals []Interval) []Interval {
     // taking care of empty condition
     if len(intervals)==0{
         return intervals
     }
     
     // sort the intervals by start time
     sort.Sort(IntervalStartSort(intervals))
     
     start, end := intervals[0].Start, intervals[0].End
     result := make([]Interval, 0)
     for _, interval := range intervals{
         if interval.Start <= end {
             end = maxInt(interval.End, end)
         } else {
             result = append(result, Interval{start, end})
             start, end = interval.Start, interval.End
         }
     }
     
     //add last element
     result = append(result, Interval{start, end})
     
     return result
 }
 
 func maxInt(a, b int) int {
     if a>b{
         return a
     }
     return b
 }