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

执行结果:通过

执行用时和内存消耗如下：

 

 

 

typedef struct {int start;int end;
}BOOKING;#define MAX_BOOK_NUM (1000)
typedef struct MyCalendar_ {BOOKING book[MAX_BOOK_NUM];int bnum;BOOKING *sorted[MAX_BOOK_NUM];int num;int conflict[MAX_BOOK_NUM];int cnum;BOOKING cbook[MAX_BOOK_NUM];struct MyCalendar_ *next;
} MyCalendar;#define MAX_OVERLAP_NUM (2)
typedef struct {MyCalendar calendar[MAX_OVERLAP_NUM];
} MyCalendarTwo;MyCalendarTwo* myCalendarTwoCreate() {MyCalendarTwo* obj = (MyCalendarTwo*)malloc(sizeof(MyCalendarTwo));memset(obj, 0, sizeof(MyCalendarTwo));int i;for (i = 0; i < MAX_OVERLAP_NUM - 1; i++) {obj->calendar[i].next = &obj->calendar[i+1];}obj->calendar[i].next = NULL;return obj;
}void myCalendarInsert(MyCalendar *obj, int pos, int start, int end) {assert(pos <= obj->num);BOOKING *b = &obj->book[obj->bnum++];b->start = start;b->end = end;memmove(&obj->sorted[pos+1], &obj->sorted[pos], sizeof(BOOKING *)*(obj->num-pos));obj->sorted[pos] = b;obj->num++;
}void myCalendarRemove(MyCalendar *obj, int pos, int num) {assert(pos >= 0);assert(pos + num <= obj->num);int size = obj->num - pos - num;memmove(&obj->sorted[pos], &obj->sorted[pos+num], sizeof(BOOKING *)*size);obj->num -= num;
}bool myCalendarCheck(MyCalendar *obj, int start, int end) {if (!obj->num) {return true;}int left = 0;int right = obj->num - 1;if (end <= obj->sorted[left]->start) {return true;}if (start >= obj->sorted[right]->end) {return true;}while(left < right) {int mid = left + (right - left) / 2;if (start > obj->sorted[mid]->start) {left = mid + 1;}else {right = mid;}}if (end > obj->sorted[left]->start) {return false;}if (left - 1 >= 0 && obj->sorted[left-1]->end > start) {return false;}return true;
}void myCalendarBookInternal(MyCalendar *obj, int start, int end) {if (!obj->num) {myCalendarInsert(obj, 0, start, end);return;}int left = 0;int right = obj->num - 1;if (end <= obj->sorted[left]->start) {myCalendarInsert(obj, 0, start, end);return;}if (start >= obj->sorted[right]->end) {myCalendarInsert(obj, obj->num, start, end);return;}while(left < right) {int mid = left + (right - left) / 2;if (start > obj->sorted[mid]->start) {left = mid + 1;}else {right = mid;}}myCalendarInsert(obj, left, start, end);return;
}bool myCalendarBook(MyCalendar *obj, int start, int end) {if (!myCalendarCheck(obj->next, start, end)) {return false;}if (!obj->num) {myCalendarInsert(obj, obj->num, start, end);return true;}int left = 0;int right = obj->num - 1;if (end <= obj->sorted[left]->start) {myCalendarInsert(obj, 0, start, end);return true;}if (start >= obj->sorted[right]->end) {myCalendarInsert(obj, obj->num, start, end);return true;}if (start >= obj->sorted[right]->start) {left = obj->num;}else if (start <= obj->sorted[0]->start) {left = 0;}else {while(left < right) {int mid = left + (right - left) / 2;if (start > obj->sorted[mid]->start) {left = mid + 1;}else {right = mid;}}}int ustart = start;int uend = end;obj->cnum = 0;int pos = left;if (left - 1 >= 0 && obj->sorted[left-1]->end > start) {BOOKING *b = obj->sorted[left-1];ustart = ustart < b->start ? ustart : b->start;uend = uend > b->end ? uend : b->end;int nstart = start;int nend = b->end < end ? b->end : end;pos--;obj->cbook[obj->cnum].start = nstart;obj->cbook[obj->cnum].end = nend;obj->conflict[obj->cnum++] = left - 1;}for (int i = left; i < obj->num; i++) {BOOKING *b = obj->sorted[i];if (end <= b->start) {break;}int nstart = b->start;int nend = b->end < end ? b->end : end;ustart = ustart < b->start ? ustart : b->start;uend = uend > b->end ? uend : b->end;obj->cbook[obj->cnum].start = nstart;obj->cbook[obj->cnum].end = nend;obj->conflict[obj->cnum++] = i;}for (int i = 0; i < obj->cnum; i++) {BOOKING *b = &obj->cbook[i];myCalendarBookInternal(obj->next, b->start, b->end);}myCalendarRemove(obj, pos, obj->cnum);myCalendarInsert(obj, pos, ustart, uend);return true;
}bool myCalendarTwoBook(MyCalendarTwo* obj, int start, int end) {MyCalendar *c = &obj->calendar[0];bool success = myCalendarBook(c, start, end);return success;
}void myCalendarTwoFree(MyCalendarTwo* obj) {free(obj);
}

解题思路：

这段代码实现了一个二级日历预约系统，允许用户在不同的日历上预约时间段，并检查预约是否存在冲突。下面是代码的详细思路：

数据结构设计

1. BOOKING 结构体：
   • 存储单个预约的起始时间 start 和结束时间 end。
2. MyCalendar 结构体：
   • book 数组：存储所有预约的详细信息。
   • bnum：当前已存储的预约数量。
   • sorted 指针数组：存储指向 book 数组中预约的指针，这些预约按起始时间排序。
   • num：sorted 数组中存储的预约数量。
   • conflict 数组：用于存储冲突预约在 sorted 数组中的索引。
   • cnum：当前冲突的数量。
   • cbook 数组：用于临时存储冲突预约的合并结果。
   • next 指针：指向下一个 MyCalendar 实例，用于实现二级日历系统。
3. MyCalendarTwo 结构体：
   • calendar 数组：存储多个 MyCalendar 实例，实现二级日历系统。这里只使用了两个日历的索引空间（MAX_OVERLAP_NUM 定义为 2），但实际上可以扩展以支持更多日历。

函数实现

1. myCalendarTwoCreate 函数：
   • 创建一个 MyCalendarTwo 实例。
   • 初始化所有成员变量。
   • 将 MyCalendar 实例链接成一个单向链表（尽管这里只使用了两个实例，链表的概念仍然适用）。
2. myCalendarInsert 函数：
   • 在 sorted 数组的指定位置插入一个新的预约。
   • 使用 memmove 函数移动元素以腾出空间。
3. myCalendarRemove 函数：
   • 从 sorted 数组中删除指定数量的预约。
   • 使用 memmove 函数移动元素以覆盖被删除的元素。
4. myCalendarCheck 函数：
   • 检查一个新的预约是否与现有的预约冲突。
   • 使用二分查找提高查找效率。
5. myCalendarBookInternal 函数：
   • 在不考虑冲突检查的情况下，将一个预约插入到 MyCalendar 实例中。
   • 使用二分查找确定插入位置。
6. myCalendarBook 函数：
   • 检查并尝试在 MyCalendar 实例中预约一个时间段。
   • 如果存在冲突，则尝试在下一级日历（next 指向的日历）中预约冲突部分。
   • 更新当前日历中的预约，合并冲突预约并删除旧的冲突预约。
7. myCalendarTwoBook 函数：
   • 在二级日历系统中预约一个时间段。
   • 目前只使用了第一个 MyCalendar 实例进行预约。
8. myCalendarTwoFree 函数：
   • 释放 MyCalendarTwo 实例所占用的内存。

总结

这段代码实现了一个复杂的二级日历预约系统，具有以下特点：

• 支持在多个级别上进行预约。
• 使用二分查找提高查找效率。
• 能够处理预约冲突，并尝试在下一级日历中预约冲突部分。
• 提供了创建、预约和释放资源的接口。

然而，代码中存在一些潜在的问题和改进点：

• MyCalendar 实例之间的链表连接仅用于实现二级日历的概念，但实际上并未充分利用这一结构。在当前的实现中，只使用了第一个 MyCalendar 实例。
• 内存管理需要谨慎处理，特别是在释放资源时，要确保不会泄露内存或访问已释放的内存。
• 代码的可读性和可维护性可以通过更好的注释和重构来提高。