题目链接: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(n2)其中 n 表示日程安排的数量。由于每次在进行预定时,都需要遍历所有已经预定的行程安排。
- 空间复杂度:O(n),其中 n 表示日程安排的数量。需要保存所有已经预定的行程。