关于leetcode个人解题总结:leetcode729我的日程安排表

题目形容

要害思维

日程列表中依照程序排序:不便大小比拟

  1. 首先进行大略的区间判断:通过二分查找初步确认应该插入的地位(index)
  2. 判断插入日程是否与(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
 };

一些细节和纳闷

  1. 在二分查找中寻找两头数:
  2. 判断条件的程序问题:
  3. 为什么index=l-1:

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据