57.insert-interval.go

/*
 * @lc app=leetcode id=57 lang=golang
 *
 * [57] Insert Interval
 *
 * https://leetcode.com/problems/insert-interval/description/
 *
 * algorithms
 * Medium (36.84%)
 * Likes:    5851
 * Dislikes: 400
 * Total Accepted:    591.6K
 * Total Submissions: 1.6M
 * Testcase Example:  '[[1,3],[6,9]]\n[2,5]'
 *
 * You are given an array of non-overlapping intervals intervals where
 * intervals[i] = [starti, endi] represent the start and the end of the i^th
 * interval and intervals is sorted in ascending order by starti. You are also
 * given an interval newInterval = [start, end] that represents the start and
 * end of another interval.
 *
 * Insert newInterval into intervals such that intervals is still sorted in
 * ascending order by starti and intervals still does not have any overlapping
 * intervals (merge overlapping intervals if necessary).
 *
 * Return intervals after the insertion.
 *
 *
 * Example 1:
 *
 *
 * Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
 * Output: [[1,5],[6,9]]
 *
 *
 * Example 2:
 *
 *
 * Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * Output: [[1,2],[3,10],[12,16]]
 * Explanation: Because the new interval [4,8] overlaps with
 * [3,5],[6,7],[8,10].
 *
 *
 *
 * Constraints:
 *
 *
 * 0 <= intervals.length <= 10^4
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 10^5
 * intervals is sorted by starti in ascending order.
 * newInterval.length == 2
 * 0 <= start <= end <= 10^5
 *
 *
 */

// @lc code=start
func insert(intervals [][]int, newInterval []int) [][]int {
	retVal, i := [][]int{}, 0
	start, end := newInterval[0], newInterval[1]
	for ; i < len(intervals) && intervals[i][1] < start; i++ {
		retVal = append(retVal, intervals[i])
	}

	for ; i < len(intervals) && intervals[i][0] <= end; i++ {
		start = Min(intervals[i][0], start)
		end = Max(intervals[i][1], end)
	}
	retVal = append(retVal, []int{start, end})

	for ; i < len(intervals); i++ {
		retVal = append(retVal, intervals[i])
	}
	return retVal
}

func Max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func Min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end