我的日程安排表 III

内容：

实现一个 MyCalendar 类来存放你的日程安排，你可以一直添加新的日程安排

MyCalendar 有一个 book(int start, intend)方法。它意味着在start到end时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，

start <= x < end。

当 K 个日程安排有一些时间上的交叉时（例如K个日程安排都在同一时间内），就会产生 K 次预订。

每次调用 MyCalendar.book方法时，返回一个整数 K ，表示最大的 K 次预订。

请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar();

MyCalendar.book(start, end)

示例 1:

MyCalendarThree();MyCalendarThree.book(10, 20); // returns 1MyCalendarThree.book(50, 60); // returns 1MyCalendarThree.book(10, 40); // returns 2MyCalendarThree.book(5, 15); // returns 3MyCalendarThree.book(5, 10); // returns 3MyCalendarThree.book(25, 55); // returns 3

解释:

前两个日程安排可以预订并且不相交，所以最大的K次预订是1。

第三个日程安排[10,40]与第一个日程安排相交，最高的K次预订为2。

其余的日程安排的最高K次预订仅为3。

请注意，最后一次日程安排可能会导致局部最高K次预订为2，但答案仍然是3，原因是从开始到最后，时间[10,20]，[10,40]和[5,15]仍然会导致3次预订。

说明:

每个测试用例，调用 MyCalendar.book 函数最多不超过 400次。

调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。

代码如下：

class MyCalendarThree():    def __init__(self):        self.time_lines = []    def book(self, start, end):        self.time_lines+= [[start, 1], [end, -1]]        self.time_lines.sort()                result = 0          c_sum = 0          # 遍历列表        for temp in self.time_lines:            c_sum += temp[1]              result = max(c_sum, result)        return resultmycalendar = MyCalendarThree()print(mycalendar.book(10, 20))print(mycalendar.book(50, 60))print(mycalendar.book(10, 40))print(mycalendar.book(5, 15))print(mycalendar.book(5, 10))print(mycalendar.book(25, 55))# 结果如下：112333

分析：

1.我们把每一个开始时间start的这个时刻的计数加1，把结束时间end的这个时刻计数-1；

2.按时间顺序排列从小到大；

3.按时间线从前往后遍历，首先遍历到的肯定是一个开始时间，这里的值一定是正数，表示从这个时候开始，后面这段时间有多少件事情正在执行（ongoing）。此后，若又遇到正数则说明这里又新的事件在执行，需要累加起来；同理，若遇到负数则说明有事件到这里结束了。

4.我们此题需求的是任意时间内同时发生的最大事件数，所以，累加过程中的最大值即为结果。

参考文献：

总结：还需要更努力，追上大佬的步伐！

转载地址：http://ppwpi.baihongyu.com/

你可能感兴趣的文章