leetcode|729-我的日程安排表 leetcode个人解题总结

题目描述

文章图片

关键思想
【leetcode|729-我的日程安排表】日程列表中按照顺序排序：方便大小比较

首先进行大概的区间判断：通过二分查找初步确认应该插入的位置(index)
判断插入日程是否与(index)相邻日程重叠，若无重叠则添加返回true，重叠则插入失败返回false。可以插入的几种情况：

情况一：index为0，也就是说插入日程前面没有日程了，若插入日程的结束日期比日程表第一个日程开始时间还早：end<=schedule[0][0]
情况二：index不为0，若插入日程的开始日期比前一个日程的结束日期晚，并且插入日程的结束日期比下一个日程的开始日期早：start>=schedule[index][1]&&end<=this.schedule[index+1][0]（因为左开右闭）
情况三：index不为0，若插入日程的开始日期比前一个日程的结束日期晚，并且后面没有日程了，可以直接插入:start>=schedule[index][1]&&index+1>=len

代码实现

var MyCalendar = function() { this.schedule = []; }; /** * @param {number} start * @param {number} end * @return {boolean} */ MyCalendar.prototype.book = function(start, end) { const len=this.schedule.length; //如果此时日程表中无日程，则直接添加日程 if (len === 0) { this.schedule.push([start, end]); return true; } //1.二分查找 let r=len; let l=0; while(l> 1); if(this.schedule[mid][1] <= start){ l=mid+1; }else{ r=mid; } } //2.判断日程是否能插入 let index=l-1; //二分查找初步定的插入位置 let insertIndex; //最终的插入位置 if(index===-1){ if(this.schedule[0][0]>=end){ insertIndex=0; } }else{ if(start>=this.schedule[index][1]&&(index+1>=len||end<=this.schedule[index+1][0])){ insertIndex=index+1; } } //3.插入操作 if(insertIndex!==undefined){ this.schedule.splice(insertIndex,0,[start,end]); return true } return false };

一些细节和疑惑