题目形容
要害思维
日程列表中依照程序排序:不便大小比拟
- 首先进行大略的区间判断:通过二分查找初步确认应该插入的地位(
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: