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

5次阅读

共计 1169 个字符，预计需要花费 3 分钟才能阅读完成。

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

首先进行大略的区间判断：通过二分查找初步确认应该插入的地位(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
 };