INTERVIEW: Given a list of intervals, write function that will merge the overlapping intervals and return new list. For example, given [1,3],[8,10],[2,6],[15,18] return [1,6],[8,10],[15,18].

INSTRUCTIONS.md

Given a collection of intervals, merge all overlapping intervals.

For example, given [1,3],[8,10],[2,6],[15,18] return [1,6],[8,10],[15,18].

solution_1.go

package main

import (
	"fmt"
	"math"
	"sort"
)

type Interval struct {
	Lower int
	Upper int
}

func (i *Interval) SetUpper(new int) {
	i.Upper = new
}

func mergeOverlapping(intervals []Interval) []Interval {
	sort.Slice(intervals[:], func(j, k int) bool {
		return intervals[j].Lower < intervals[k].Lower
	})
	var merged []Interval

	for _, current := range intervals {
		if len(merged) == 0 {
			merged = append(merged, current)
		} else {
			previous := merged[len(merged)-1]
			if previous.Upper >= current.Lower {
				merged[len(merged)-1].SetUpper(
					int(
						math.Max(
							float64(previous.Upper),
							float64(current.Upper),
						),
					),
				)
			} else {
				merged = append(merged, current)
			}
		}
	}
	return merged
}

func main() {
	intervals := []Interval{{3, 5}, {7, 10}, {4, 8}, {12, 15}, {16, 19}}
	merged := mergeOverlapping(intervals)
	fmt.Println(merged)
}

solution_1.py

intervals = [[1,3],[8,10],[2,6],[15,18]]

def merge_overlapping(intervals):
    intervals.sort(key=lambda interval: interval[0])

    merged = list()

    for interval in intervals:
        if not merged:
            merged.append(interval)
        else:
            previous = merged[-1]

            if previous[1] >= interval[0]:            
                merged[-1] = [previous[0], max(previous[1], interval[1])]
            else:
                merged.append(interval)
                
    return merged
                                          
print(merge_overlapping(intervals))