732. My Calendar III

week13

难度：Hard

题目链接

题目描述

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

Your class will be called like this: MyCalendarThree cal = new MyCalendarThree(); MyCalendarThree.book(start, end)

Example1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation: 
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.

Note:

  • The number of calls to MyCalendarThree.book per test case will be at most 400.
  • In calls to MyCalendarThree.book(start, end), start and end are integers in the range [0, 10^9].

题目分析

  题目简单来说，就是寻找最大的重合数量，可以看作为有许多条线段在一个区间上，每加入一条线段则要得出最大的重叠数量，重叠就是指线段有一段重合的区间则这两条线段重叠。

解题思路

  这道题我想的是如果要求最大重叠数量，假如对每条线段都去遍历一遍得出重合的线段再统计的话就很麻烦，即使维护一个最大数量每次插入后比较，也并不会很好做。

  对于这个题目可以想到这么一种做法，记录下每一条线段的起点与终点，然后在这一个区间上遍历，如果遇到起点，那么此时有一条线段加入，如果遇到终点，即意味着有一条线段结束了，通过这种做法可以得出在某个点上线段有多少条，求出最大的即可。

  在数据结构上选择map可以不用考虑排序的问题，而且键值对便于修改。加入线段，线段的起点数值+1，终点-1，这样在遍历这整个区间时，直接加上该点的数值即可方便统计线段数量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MyCalendarThree
{
  public:
    map<int, int> m;
    int maximum;
    MyCalendarThree()
    {
        maximum = 0;
    }

    int book(int start, int end)
    {
        int num = 0;
        m[start]++;
        m[end]--;
        for (auto i = m.begin(); i != m.end(); ++i)
        {
            num += i->second;
            if (maximum < num)
                maximum = num;
        }
        return maximum;
    }
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree obj = new MyCalendarThree();
 * int param_1 = obj.book(start,end);
 */

结果反思

![upload successful](\images\pasted-15.png)

  这个算法虽然运行速度不快，但是胜于非常简单。。很容易理解。代码也非常简洁，就那么几行搞定，主要是要选择适合的数据结构存储。

总结

  这个方法其实是有向图的一个变形，用到了出度和入度的方法，就和我说的初始和闭合一样，到初始点数量++，到了终点数量–。所以最大数量总是在某个线段开始的地方的，因此就转变为了寻找最大的出度。