@ninijia 在 Leetcode每日一题练习 ------ 731. 我的日程安排表 II 中发帖
从Leetcode 每日一题练习继续讨论:
731. 我的日程安排表 II
731. My Calendar II
题解
本题仍然可以使用线段树求解,我们思考线段树的作用是什么,线段树使用了额外的空间保存了不断二分的区间的状态,从而对于有些区间问题,我们只需要知道这个区间拥有的某些性质即足以解决问题,没必要了解区间内的全部细节。这种区间对应了整体思想,将某些部分当作一个整体,用整体性质去求解。经典的线段树保存的是区间内全部数字的和,对于本题,我们只需修改区间保存的状态就可复用线段树解题。
本题中我们需要知道的是某个时间被访问过几次,则可以记录每个时间被访问的次数,对于区间我们可以记录该区间内这个访问次数的最大值。因为某个时间区间被预订后,该区间的所有时间的访问次数都要加1,因此仍然可以先将这个加1的状态保留在顶层的节点,在需要时再向下探索并将状态传递下去。
则我们需要构造线段树,...