LeetCode#732 My Calendar My Calendar III

题目

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)

Example 1:

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.

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

思路

简化一下，这道题的意思就是每次输入一个数据段，给出其左右边界[a, b)，并求当前最大的数据段覆盖次数。例如下图，最大的数据段覆盖次数是2，是[3, 5)、[5, 6)、[7, 8)三个数据段。

这题的基本思路是将点离散化，并且将起点当作入度，终点当出度，用一个数组node_number记录，例如数据段[a, b)，则node_number[a]++, node_number[b]–。初始化cnt=0，从最小的点开始，遇到一个点node，就cnt = cnt + node_number[node]，如果此时cnt比目前得到的覆盖数大，则更新最大覆盖数。另外，这里涉及到排序的问题，因为每次插入的序列都是已经排好序的，所以这里可以采用插入排序。

代码

#include <iostream>#include <stdio.h>#include <string>#include<string.h>#include <vector>#include <map>#include <stack>#include <algorithm>#include <stack>#include <queue>using namespace std;class MyCalendarThree {public:vector<int>v;map<int, int>node_number;int ans;MyCalendarThree() {v.clear();node_number.clear();ans = -1;}void my_sort(int number) {int i, j, k;k = v.size();for(i=0; i<k; i++) {if(v[i] > number) {break;}if(v[i] == number) {return ;}}if(i < k) {v.push_back(v[k-1]);for(j=k-1; j>i; j--) {v[j] = v[j-1];}v[j] = number;}else {v.push_back(number);}}int book(int start, int end) {if(node_number.count(start) == 0) {node_number[start] = 1;} else {node_number[start]++;}if(node_number.count(end) == 0) {node_number[end] = -1;} else {node_number[end]--;}int i, j, k, cnt=0;my_sort(start);my_sort(end);for(k=0; k<=v.size(); k++) {cnt = cnt + node_number[v[k]];if(cnt > ans) {ans = cnt;}}return ans;}};int main(){MyCalendarThree cal;int i, j, k;while(~scanf("%d %d", &i, &j)) {k = cal.book(i, j);printf("%d\n", k);}return 0;}

如果觉得《LeetCode#732 My Calendar My Calendar III》对你有帮助，请点赞、收藏，并留下你的观点哦！