leetcode-每日一题731. 我的日程安排表 II

题目链接：https://leetcode.cn/problems/my-calendar-ii/
孪生弟弟题 729. 我的日程安排表 I：https://leetcode.cn/problems/my-calendar-i/

思路

方法一、直接遍历

直接想法
题目需要我们判断在重复的预定时间里，有三重预定的返回false，那我们可以定义一个pair结构体用来表示时间段，MyCalendarTwo结构体用来存成功预定的时间段booked切片，和有重复预定的时间段overlaps切片，overlaps切片用来判断新进的时间段是否跟overlaps有重合预定的情况，若有则返回false，没有则true

代码示例

type pair struct{
     start, end int }
type MyCalendarTwo struct{
     booked, overlaps []pair }

func Constructor() MyCalendarTwo {
    
    return MyCalendarTwo{
    }
}

func (c *MyCalendarTwo) Book(start, end int) bool {
    
    for _, p := range c.overlaps {
    
        if p.start < end && start < p.end {
    
            return false
        }
    }
    for _, p := range c.booked {
    
        if p.start < end && start < p.end {
    
            c.overlaps = append(c.overlaps, pair{
    max(p.start, start), min(p.end, end)})
        }
    }
    c.booked = append(c.booked, pair{
    start, end})
    return true
}

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

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

复杂度分析

• 时间复杂度：O(n²)其中 n 表示日程安排的数量。由于每次在进行预定时，都需要遍历所有已经预定的行程安排。

• 空间复杂度：O(n)，其中 n 表示日程安排的数量。需要保存所有已经预定的行程。