题目形容
要害思维
日程列表中依照程序排序：不便大小比拟
- 首先进行大略的区间判断：通过二分查找初步确认应该插入的地位(
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<r){ let mid = l + ((r - 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 };一些细节和纳闷
- 在二分查找中寻找两头数：
- 判断条件的程序问题：
- 为什么index=l-1：