[TOC]

56. 合并区间（中等）

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

// ================ 解法一 ====================================
func merge(intervals [][]int) [][]int {
    //先从小到大排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    //再弄重复的
    for i := 0; i < len(intervals)-1; i++ {
        // 当前右边界intervals[i][1]和下一区间左边界intervals[i+1][0]比较
        if intervals[i][1] >= intervals[i+1][0] {
            // 更新区间右边界最大值
            intervals[i][1] = max(intervals[i][1], intervals[i+1][1]) //赋值最大值
            // 删除下一个区间元素，因为此时当前区间右边界已经变了
            intervals = append(intervals[:i+1], intervals[i+2:]...) // 很重要，删除i+1这一行
            i--
        }
    }
    return intervals
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

//  ====================  解法二(不易理解，建议还是用解法一)  ============================
func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    var res [][]int
    start, end := intervals[0][0], intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] <= end {
            if intervals[i][1] > end {
                end = intervals[i][1]
            }
        } else {
            res = append(res, []int{start, end})
            start, end = intervals[i][0], intervals[i][1]
        }
    }
    return append(res, []int{start, end})
}

57. 插入区间（中等）

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

func insert(intervals [][]int, newInterval []int) [][]int {
    intervals = append(intervals, newInterval)
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    //再弄重复的
    for i := 0; i < len(intervals)-1; i++ {
        // 当前右边界intervals[i][1]和下一区间左边界intervals[i+1][0]比较
        if intervals[i][1] >= intervals[i+1][0] {
            // 更新区间右边界最大值
            intervals[i][1] = max(intervals[i][1], intervals[i+1][1]) //赋值最大值
            // 删除下一个区间元素，因为此时当前区间右边界已经变了
            intervals = append(intervals[:i+1], intervals[i+2:]...) // 很重要，删除i+1这一行
            i--
        }
    }
    return intervals
}

163. 缺失的区间（会员/简单）

给定一个排序的整数数组 nums ，其中元素的范围在 闭区间 [lower, upper] 当中，返回不包含在数组中的缺失区间。

输入: nums = [0, 1, 3, 50, 75], lower = 0 和 upper = 99,
输出: ["2", "4->49", "51->74", "76->99"]

func main() {
    nums := []int{0, 1, 3, 50, 75}
    lower := 0
    upper := 99
    fmt.Println(findMissingRanges(nums, lower, upper))
}

func CreateResult(start, end int) (str string) {
    if start == end {
        //return string(start)
        str = fmt.Sprintf("%d", start)
    } else {
        //return string(start)+"->"+string(end)
        str = fmt.Sprintf("%d->%d", start, end)
    }

    return str
}

func CreateParts(newNums []int, lower int, upper int) []string {
    if len(newNums) == 0 {
        return []string{CreateResult(lower, upper)}
    }
    result := make([]string, 0)
    // 这里是左边界
    if lower < newNums[0] {
        result = append(result, CreateResult(lower, newNums[0]-1))
    }
    //这里是主体，注意这里长度是-1
    for i := 0; i < len(newNums)-1; i++ {
        if newNums[i+1]-1 <= newNums[i] {
            continue
        }
        result = append(result, CreateResult(newNums[i]+1, newNums[i+1]-1))
    }
    //这里是右边界
    if upper > newNums[len(newNums)-1] {
        result = append(result, CreateResult(newNums[len(newNums)-1]+1, upper))
    }

    return result
}

func findMissingRanges(nums []int, lower int, upper int) []string {
    if len(nums) == 0 {
        return []string{CreateResult(lower, upper)}
    }
    newNums := make([]int, 0)
    for i := 0; i < len(nums); i++ {
        if nums[i] < lower || nums[i] > upper {
            continue
        }
        newNums = append(newNums, nums[i])
    }
    return CreateParts(newNums, lower, upper)
}

1272. 删除区间（会员/中等）

实数集合可以表示为若干不相交区间的并集，其中每个区间的形式为 [a, b)（左闭右开），表示满足 a <= x < b 的所有实数  x 的集合。如果某个区间 [a, b) 中包含实数 x ，则称实数 x 在集合中。

给你一个 有序的 不相交区间列表 intervals 。intervals 表示一个实数集合，其中每一项 intervals[i] = [ai, bi] 都表示一个区间 [ai, bi) 。再给你一个要删除的区间 toBeRemoved 。

返回 一组实数，该实数表示intervals 中 删除 了 toBeRemoved 的部分 。换句话说，返回实数集合，并满足集合中的每个实数 x 都在 intervals 中，但不在 toBeRemoved 中。你的答案应该是一个如上所述的 有序的 不相连的间隔列表 。

输入：intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
输出：[[0,1],[6,7]]

输入：intervals = [[0,5]], toBeRemoved = [2,3]
输出：[[0,2],[3,5]]

输入：intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]
输出：[[-5,-4],[-3,-2],[4,5],[8,9]]

func main() {
    intervals := [][]int{
        {0, 2},
        {3, 4},
        {5, 7},
    }
    toBeRemoved := []int{1, 6}
    result := removeInterval(intervals, toBeRemoved)
    fmt.Println(result)
}

func removeInterval(intervals [][]int, toBeRemoved []int) [][]int {
    //先从小到大排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    var res [][]int
    for i := 0; i < len(intervals); i++ {
        start, end := intervals[i][0], intervals[i][1]
        if start >= toBeRemoved[1] || end <= toBeRemoved[0] {
            res = append(res, []int{start, end})
        } else {
            if start < toBeRemoved[0] {
                res = append(res, []int{start, toBeRemoved[0]})
            }

            if end > toBeRemoved[1] {
                res = append(res, []int{toBeRemoved[1], end})
            }
        }
    }
    return res
}

252. 会议室（会员/简单）

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

输入：intervals = [[0,30],[5,10],[15,20]]
输出：false

输入：intervals = [[7,10],[2,4]]
输出：true

func main() {
    intervals := [][]int{
        {0, 30},
        {5, 10},
        {15, 20},
    }

    result := canAttendMeetings(intervals)
    fmt.Println(result)
}

func canAttendMeetings(intervals [][]int) bool {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    fmt.Println(intervals)

    for i := 0; i < len(intervals)-1; i++ {
        if intervals[i][1] > intervals[i+1][0] {
            return false
        }
    }
    return true
}

253. 会议室 II（会员/中等）

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

输入：intervals = [[7,10],[2,4]]
输出：1

/*//  ====================== 解法一：数飞机解法 =======================
// 其实这种做法就是数飞机法，这里是全都乘以10，然后加了标记1或者2的。
本题可以先假设只有一个大大大会议室，参加不同会议的人都可以自由进出会议室，咱们只要看到同一时间会议室内最多有几批人，就知道需要几个会议了。

咱们的做法是：
1、先把进出时间从小到大进行排序。
这里有个小技巧，怎么样区分哪个是进，哪个是出呢？只要加个标志位就好了。【这里其实就是数飞机的思路了】
为了不影响原数大小，所有数值*10后，再加上标志位，进为2，出为1。
为什么进要大一点呢？因为如果A组人员刚出，B组就进来了，那么可以认为一个会议室是可以容纳这两组人开会的。所以，咱们先出后进，防止多算。
2、如果有人进房间，那么需要的会议室数量curNeedRoom就+1，反之，有人出房间，curNeedRoom就-1。
3、记录下curNeedRoom的最大值，就是咱们需要的会议室
*/
func minMeetingRooms(intervals [][]int) int {
    var nums []int
    for _, v := range intervals {
        nums = append(nums, v[0]*10+2) // 进为2
        nums = append(nums, v[1]*10+1) // 出为1，排序要从小到大，先出后进。
    }
    sort.Ints(nums)
    maxRoom := 0
    curNeedRoom := 0
    for _, v := range nums {
        if v%10 == 1 {
            curNeedRoom--
        } else {
            curNeedRoom++
        }
        if curNeedRoom > maxRoom {
            maxRoom = curNeedRoom
        }
    }
    return maxRoom
}


/*
================== 解法二 =======================
下面的整体思路是：
第一步：拆分为两个数组，一个start，一个end
第二步：将两个数组分别排序
第三步：遍历单数组，如果开始时间<结束时间，room++，否则endItr增加
*/
func minMeetingRooms(intervals [][]int) int {
    n := len(intervals)
    begin, end := make([]int, n), make([]int, n)
    for i := 0; i < n; i++ {
        begin[i] = intervals[i][0]
        end[i] = intervals[i][1]
    }
    sort.Ints(begin) //递增的开始时间数组
    sort.Ints(end)   //递增的结束时间数组

    endItr, cnt := 0, 0
    for i := 0; i < n; i++ { // 只要把startTime从头到位弄完就行
        if begin[i] < end[endItr] { // 如果开始时间小于最近的结束时间，则会议室数量加1,接着到第二个starttime,如果还小于endTime，肯定还要一个房间
            cnt++
        } else {
            endItr++
        }
    }
    return cnt
}

// =========== 解法三：差分 =============
func minMeetingRooms(intervals [][]int) int {
    nums := make([]int, 1000001) // 这里是时间 0 <= starti < endi <= 106
    var df Difference
    df.init(nums)
    for _, interval := range intervals {
        df.increment(interval[0], interval[1]-1, 1) // interval[0]时刻使用, interval[1]-1用完
    }
    res := df.result()
    return maxValInSlice(res)
}

func maxValInSlice(input []int) int {
    maxVal := input[0]
    for i := range input {
        if input[i] > maxVal {
            maxVal = input[i]
        }
    }
    return maxVal
}

435. 无重叠区间（中等）

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    fmt.Println(intervals)

    count := 1
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= end { // /当区间的左边界大于上一个区间的右边界的时候 说明是一对不重合区间
            count++
            end = intervals[i][1]
        }
    }
    return len(intervals) - count // //intervals的长度减去最多的不重复的区间 就是最少删除区间的个数
}

1288. 删除被覆盖区间（中等）

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
在完成所有删除操作后，请你返回列表中剩余区间的数目。

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

352. 将数据流变为多个不相交区间（困难）

1229. 安排会议日程（会员/中等/务必做一下）

给定两个人的空闲时间表：slots1 和 slots2，以及会议的预计持续时间 duration，请你为他们安排 时间段最早 且合适的会议时间。如果没有满足要求的会议时间，就请返回一个 空数组。「空闲时间」的格式是 [start, end]，由开始时间 start 和结束时间 end 组成，表示从 start 开始，到 end 结束。 

题目保证数据有效：同一个人的空闲时间不会出现交叠的情况，也就是说，对于同一个人的两个空闲时间 [start1, end1] 和 [start2, end2]，要么 start1 > end2，要么 start2 > end1。

输入：slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
输出：[60,68]

输入：slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
输出：[]

986. 区间列表的交集（中等）

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。返回这 两个区间列表的交集 。形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]

输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]

输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

759. 员工空闲时间（会员/困难/务必做一下）

给定员工的 schedule 列表，表示每个员工的工作时间。每个员工都有一个非重叠的时间段  Intervals 列表，这些时间段已经排好序。
返回表示 所有 员工的 共同，正数长度的空闲时间 的有限时间段的列表，同样需要排好序。

输入：schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
输出：[[3,4]]
解释：
共有 3 个员工，并且所有共同的
空间时间段是 [-inf, 1], [3, 4], [10, inf]。
我们去除所有包含 inf 的时间段，因为它们不是有限的时间段。

输入：schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
输出：[[5,6],[7,9]]

218. 天际线问题（困难）

城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。

天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]

输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。