扫描线

leetcode 252

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
}

leetcode 253（扫描线）

题目： 给你一个会议时间安排的数组 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
}

56 合并区间

// ================ 解法一 ====================================
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 插入区间（解法完全同56，可直接转化为56求解）

1272 删除区间

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

}