LeetCode: Insert Interval

Posted on January 13, 2018July 26, 2020 by braindenny

Insert Interval

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/insert-interval
// Basic Ideas: merge two list + binarysearch
//
// Loop intervals, if they doesn't overlap, insert
//      Otherwise hold on. Until it finally doesn't overlap
//
// Complexity: Time O(n), Space O(1)
func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}

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

func insert(intervals [][]int, newInterval []int) [][]int {
    res := [][]int{}
    for _, interval := range intervals {
        // solved already
        if len(newInterval) == 0 {
            res = append(res, interval)
            continue
        }
        x1, y1 := interval[0], interval[1]
        x2, y2 := newInterval[0], newInterval[1]
        if min(y1, y2) < max(x1, x2) {
            // Doesn't overlap
            if x1>x2 {
                res = append(res, newInterval)
                newInterval = []int{}
            }
            res = append(res, interval)
        } else {
            newInterval = []int{min(x1, x2), max(y1, y2)}
        }
    }
    if len(newInterval) != 0 {
       res = append(res, newInterval) 
    }
    return res
}

Post Views: 5