Insert Interval

描述

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.


Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].



Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].



This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

题解

package algorithms

import "github.com/ljun20160606/leetcode/algorithms"

/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */

type Interval = algorithms.Interval

func insert(intervals []Interval, newInterval Interval) []Interval {
	if len(intervals) == 0 {
		return []Interval{newInterval}
	}
	ret := make([]Interval, 0)
	prev := newInterval
	idx := 0
	for idx < len(intervals) {
		if intervals[idx].Start < prev.Start {
			if isIntersect(intervals[idx], prev) {
				prev = merge(intervals[idx], prev)
			} else {
				ret = append(ret, intervals[idx])
			}
		} else {
			if isIntersect(prev, intervals[idx]) {
				prev = merge(prev, intervals[idx])
			} else {
				ret = append(ret, prev)
				prev = intervals[idx]
			}
		}
		idx++
	}
	ret = append(ret, prev)
	return ret
}

func isIntersect(a Interval, b Interval) bool {
	return a.End >= b.Start
}

func merge(a Interval, b Interval) Interval {
	if a.End < b.End {
		return Interval{Start: a.Start, End: b.End}
	}
	return a
}