Leecode刷题C语言之我的日程安排表③

实行效果:通过
实行用时和内存斲丧如下：

 

 

2. typedef struct {
3.     int size;
4.     int maxIntersection;
5.     int** books;
6.     // #ifdef DEBUG
7.     // int runCount;
8.     // #endif
9. } MyCalendarThree;
11. void insert(MyCalendarThree*, int, int, int, int);
12. int* binarySearch(int*, int, int);
14. MyCalendarThree* myCalendarThreeCreate() {
15.     MyCalendarThree* newCal = (MyCalendarThree*)malloc(sizeof(MyCalendarThree));
16.     newCal -> size = 0;
17.     newCal -> maxIntersection = 0;
18.     newCal -> books = (int**)malloc(sizeof(int*) * 2);
19.     for (int i = 0; i < 2; i++) {
20.         (newCal -> books)[i] = (int*)malloc(sizeof(int) * 400);
21.     }
22.     // #ifdef DEBUG
23.     // newCal -> runCount = 0;
24.     // #endif
26.     return newCal;
27. }
29. int myCalendarThreeBook(MyCalendarThree* obj, int startTime, int endTime) {
30.     //printf("New Process\n");
31.     int* sLoc = binarySearch((obj -> books)[0], obj -> size, startTime);
32.     int* eLoc = binarySearch((obj -> books)[1], obj -> size, startTime);
33.     int initialSLoc = (int)(sLoc - (obj -> books)[0]);
34.     int eeLoc = (int)(binarySearch((obj -> books)[1], obj -> size, endTime) - (obj -> books)[1]);
35.     //printf("Initial: %d, %d\n", initialSLoc, (int)(eLoc - (obj -> books)[1]));
36.     int count = initialSLoc - (int)(eLoc - (obj -> books)[1]) + 1;
37.     // #ifdef DEBUG
38.     // DEBUG(9);
39.     // #endif
40.     while (*sLoc < endTime) {
41.         if (count > obj -> maxIntersection) obj -> maxIntersection = count;
42.         if ((int)(sLoc - (obj -> books)[0]) >= obj -> size) {
43.             break;
44.         }
45.         //printf("count: %d\n", count);
46.         if (*sLoc < *eLoc) { sLoc++; count++; }
47.         else { eLoc++; count--; }
48.     }
49.     if (count > obj -> maxIntersection) obj -> maxIntersection = count;
50.     insert(obj, startTime, endTime, initialSLoc, eeLoc);
51.     //printf("True, size=%d\n", obj -> size);
52.     return obj -> maxIntersection;
53. }
55. void myCalendarThreeFree(MyCalendarThree* obj) {
56.     for (int i = 0; i < 2; i++) {
57.         free((obj -> books)[i]);
58.     }
59.     free(obj -> books);
60.     free(obj);
61. }
63. /**
64. * Your MyCalendarThree struct will be instantiated and called as such:
65. * MyCalendarThree* obj = myCalendarThreeCreate();
66. * int param_1 = myCalendarThreeBook(obj, startTime, endTime);
68. * myCalendarThreeFree(obj);
69. */
71. int* binarySearch(int* arr, int size, int target) {
72.     int l = 0;
73.     int r = size - 1;
74.     while (l <= r) {
75.         int i = (l + r) / 2;
76.         if (target >= arr[i]) l = i + 1;
77.         else r = i - 1;
78.     }
79.     return arr + l;
80. }
82. void insert(MyCalendarThree* obj, int startTime, int endTime, int sIdx, int eIdx) {
83.     memmove(
84.         (obj -> books)[0] + sIdx + 1,
85.         (obj -> books)[0] + sIdx,
86.         (obj -> size - sIdx) * sizeof(int)
87.     );
88.     memmove(
89.         (obj -> books)[1] + eIdx + 1,
90.         (obj -> books)[1] + eIdx,
91.         (obj -> size - eIdx) * sizeof(int)
92.     );
93.     (obj -> books)[0][sIdx] = startTime;
94.     (obj -> books)[1][eIdx] = endTime;
95.     (obj -> size)++;
96. }

复制代码

 解题思绪：
这段代码实现了一个名为 MyCalendarThree 的数据结构，用于跟踪在一段时间内（由开始时间和竣事时间界说）的日程安排，并盘算在任何给定时间点同时存在的最大日程数。下面是代码的思绪分析：
数据结构界说

• MyCalendarThree 结构体包罗以下成员：
  
  
  
  • int size：当前已存储的日程数目。
    
  • int maxIntersection：在任何给定时间点同时存在的最大日程数。
    
  • int** books：一个二维数组，此中 books[0] 存储全部日程的开始时间，books[1] 存储全部日程的竣事时间。如许做可以方便地通过二分查找定位开始和竣事时间。
    
  • 解释掉的 #ifdef DEBUG 部分用于调试，不在生产代码中启用。
    
  
  

函数实现

• myCalendarThreeCreate：
  
  
  
  • 分配并初始化 MyCalendarThree 结构体。
    
  • 初始化 size 为 0，maxIntersection 为 0。
    
  • 为 books 分配内存，初始化为存储两个包罗 400 个整数的数组（预设巨细，可以根据须要调解）。
    
  • 返回创建的 MyCalendarThree 实例。
    
  
  
• binarySearch：
  
  
  
  • 在给定的数组 arr 中查找第一个大于或即是 target 的元素的指针。
    
  • 利用二分查找算法进步查找服从。
    
  • 返回指向找到的位置的指针。
    
  
  
• myCalendarThreeBook：
  
  
  
  • 利用 binarySearch 找到新日程的开始时间和竣事时间在 books 中的位置。
    
  • 盘算初始的重叠数目（基于二分查找效果）。
    
  • 遍历受影响的日程区间，更新 maxIntersection，并根据须要调解 count（重叠数目）。
    
  • 利用 insert 函数将新日程的开始和竣事时间插入到 books 中。
    
  • 返回当前的 maxIntersection。
    
  
  
• insert：
  
  
  
  • 利用 memmove 函数为新的日程在 books 数组中腾出空间。
    
  • 将新日程的开始和竣事时间插入到准确的位置。
    
  • 更新 size。
    
  
  
• myCalendarThreeFree：
  
  
  
  • 开释 MyCalendarThree 结构体中分配的全部内存。
    
  
  

利用流程

• 创建一个 MyCalendarThree 实例。
  
• 利用 myCalendarThreeBook 函数添加日程，并获取当前的 maxIntersection。
  
• 当不再须要时，利用 myCalendarThreeFree 开释 MyCalendarThree 实例占用的内存。
  

关键点

• 时间复杂度：
  
  
  
  • binarySearch：O(log n)，此中 n 是 books 中的日程数目。
    
  • myCalendarThreeBook：在最坏环境下，须要遍历全部日程来盘算重叠，但由于利用了二分查找定位新日程的位置，以是团体复杂度仍较低。
    
  
  
• 空间复杂度：
  
  
  
  • 预设了 400 个元素的数组来存储日程的开始和竣事时间，这是根据预期利用环境举行的一个折衷。如果日程数目高出这个预设值，大概须要重新筹划数据结构以动态扩展数组。