差分数组（有序集合 TreeMap）：求解《729. 我的日程安排表 I》《剑指 Offer II 058. 日程表》《731. 我的日程安排表 II》和《732. 我的日程安排表 III》
2022-06-06 16:16:43
差分数组（有序集合 TreeMap），求解《729. 我的日程安排表 I》《剑指 Offer II 058. 日程表》《731. 我的日程安排表 II》和《732. 我的日程安排表 III》
例题
729. 我的日程安排表 I
剑指 Offer II 058. 日程表
请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。
每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
答案
有序集合
MyCalendar.prototype.book = function(start, end) { // Object 实现
const sortedKeys = Object.keys(this.treeMap), n = sortedKeys.length
const l = this.floor_bound(sortedKeys, start), r = this.upper_bound(sortedKeys, start)
if ((l < 0 || l >= n || start >= this.treeMap[sortedKeys[l]]) && (r < 0 || r >= n || end <= sortedKeys[r])) {
this.treeMap[start] = end
return true
}
return false
};
MyCalendar.prototype.upper_bound = function(nums, num) {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}
MyCalendar.prototype.floor_bound = function(nums, num) {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] <= num) l = m + 1
else r = m - 1
}
return r
}class MyCalendar { // Object 实现
treeMap: Object
constructor() {
this.treeMap = Object.create(null)
}
book(start: number, end: number): boolean {
const sortedKeys = Object.keys(this.treeMap), n = sortedKeys.length
const l = this.floor_bound(sortedKeys, start), r = this.upper_bound(sortedKeys, start)
if ((l < 0 || l >= n || start >= this.treeMap[sortedKeys[l]]) && (r < 0 || r >= n || end <= +sortedKeys[r])) {
this.treeMap[start] = end
return true
}
return false
}
upper_bound(nums: string[], num: number): number {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (+nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}
floor_bound(nums: string[], num: number): number {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (+nums[m] <= num) l = m + 1
else r = m - 1
}
return r
}
}type MyCalendar struct {
treeMap map[int]int
}
func Constructor() MyCalendar {
return MyCalendar{map[int]int{}}
}
func (this *MyCalendar) Book(start int, end int) bool {
sortedKeys := getKeys(this.treeMap)
sort.Ints(sortedKeys)
l, r, n := floor_bound(sortedKeys, start), upper_bound(sortedKeys, start), len(sortedKeys)
if (l < 0 || l >= n || start >= this.treeMap[sortedKeys[l]]) && (r < 0 || r >= n || end <= sortedKeys[r]) {
this.treeMap[start] = end
return true
}
return false
}
func getKeys (treeMap map[int]int) []int {
var keys []int
for key := range treeMap {
keys = append(keys, key)
}
return keys
}
func upper_bound (nums []int, num int) int {
return sort.Search(len(nums), func(i int) bool {
return nums[i] >= num
})
}
func floor_bound (nums []int, num int) int {
l, r := 0, len(nums) - 1
for l <= r {
m := (l + r) >> 1
if nums[m] <= num {
l = m + 1
} else {
r = m - 1
}
}
return r
}class MyCalendar {
private $treeMap = array();
function __construct() {}
function book($start, $end) {
$sortedKeys = array_keys($this->treeMap);
$n = count($sortedKeys);
$l = $this->floor_bound($sortedKeys, $start);
$r = $this->upper_bound($sortedKeys, $start);
if (
($l < 0 || $l >= $n || $start >= $this->treeMap[$sortedKeys[$l]]) &&
($r < 0 || $r >= $n || $end <= $sortedKeys[$r])
) {
$this->treeMap[$start] = $end;
ksort($this->treeMap);
return true;
}
return false;
}
function upper_bound($nums, $num) {
$l = 0;
$r = count($nums) - 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($nums[$m] >= $num) $r = $m - 1;
else $l = $m + 1;
}
return $l;
}
function floor_bound($nums, $num) {
$l = 0;
$r = count($nums) - 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($nums[$m] <= $num) $l = $m + 1;
else $r = $m - 1;
}
return $r;
}
}class MyCalendar {
private TreeMap<Integer, Integer> treeMap;
public MyCalendar() {
treeMap = new TreeMap<Integer, Integer>();
}
public boolean book(int start, int end) {
Integer l = treeMap.floorKey(start);
Integer r = treeMap.ceilingKey(start);
if ((l == null || start >= treeMap.get(l)) && (r == null || end <= r)) {
treeMap.put(start, end);
return true;
}
return false;
}
}731. 我的日程安排表 II
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。
每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
答案
差分数组
var MyCalendarTwo = function() { // Object 实现
this.treeMap = Object.create(null)
};
MyCalendarTwo.prototype.book = function(start, end) {
this.treeMap[start] = (this.treeMap[start] || 0) + 1
this.treeMap[end] = (this.treeMap[end] || 0) - 1
let maxBook = 0
for (const book of Object.values(this.treeMap)) {
maxBook += book
if (maxBook === 3) {
if (--this.treeMap[start] === 0) delete this.treeMap[start]
this.treeMap[end]++
return false
}
}
return true
};class MyCalendarTwo { // Object 实现
treeMap: Object
constructor() {
this.treeMap = Object.create(null)
}
book(start: number, end: number): boolean {
this.treeMap[start] = (this.treeMap[start] || 0) + 1
this.treeMap[end] = (this.treeMap[end] || 0) - 1
let maxBook = 0
for (const book of Object.values(this.treeMap)) {
maxBook += book
if (maxBook === 3) {
this.treeMap[end]++
if (--this.treeMap[start] === 0) delete this.treeMap[start]
return false
}
}
return true
}
}class MyCalendarTwo { // array 实现
private $treeMap = array();
function __construct() {}
function book($start, $end) {
$this->treeMap[$start]++;
$this->treeMap[$end] = ($this->treeMap[$end] ?? 0) - 1;
ksort($this->treeMap);
$maxBook = 0;
foreach (array_values($this->treeMap) as $book) {
$maxBook += $book;
if ($maxBook === 3) {
if (--$this->treeMap[$start] === 0) unset($this->treeMap[$start]);
$this->treeMap[$end]++;
return false;
}
}
return true;
}
}class MyCalendarTwo {
private TreeMap<Integer, Integer> treeMap;
public MyCalendarTwo() {
treeMap = new TreeMap<Integer, Integer>();
}
public boolean book(int start, int end) {
treeMap.put(start, treeMap.getOrDefault(start, 0) + 1);
treeMap.put(end, treeMap.getOrDefault(end, 0) - 1);
int maxBook = 0;
for (int book : treeMap.values()) {
maxBook += book;
if (maxBook == 3) {
treeMap.put(start, treeMap.get(start) - 1);
treeMap.put(end, treeMap.get(end) + 1);
return false;
}
}
return true;
}
}from sortedcontainers import SortedDict
class MyCalendarTwo:
def __init__(self):
self.treeMap = SortedDict()
def book(self, start: int, end: int) -> bool:
self.treeMap[start] = self.treeMap.get(start, 0) + 1
self.treeMap[end] = self.treeMap.get(end, 0) - 1
maxBook = 0
for book in self.treeMap.values():
maxBook += book
if maxBook == 3:
self.treeMap[start] -= 1
if self.treeMap == 0: this.treeMap.pop(start)
self.treeMap[end] += 1
return False
return True732. 我的日程安排表 III
当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。
给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。
实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。
MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。
答案
差分数组
var MyCalendarThree = function() { // Object 实现
this.treeMap = Object.create(null)
};
MyCalendarThree.prototype.book = function(start, end) {
this.treeMap[start] = (this.treeMap[start] || 0) + 1
this.treeMap[end] = (this.treeMap[end] || 0) - 1
let r = maxBook = 0
for (const book of Object.values(this.treeMap)) {
maxBook += book
r = Math.max(r, maxBook)
}
return r
}; class MyCalendarThree { // Object 实现
treeMap: Object
constructor() {
this.treeMap = Object.create(null)
}
book(start: number, end: number): number {
this.treeMap[start] = (this.treeMap[start] || 0) + 1
this.treeMap[end] = (this.treeMap[end] || 0) - 1
let maxBook = 0
let r = 0
for (const book of Object.values(this.treeMap)) {
maxBook += book
r = Math.max(r, maxBook)
}
return r
}
}type MyCalendarThree struct { // blackredtree 实现
*redblacktree.Tree
}
func Constructor() MyCalendarThree {
return MyCalendarThree{redblacktree.NewWithIntComparator()}
}
func (this *MyCalendarThree) Add(start int, value int) {
if v, ok := this.Get(start); ok {
value += v.(int)
}
this.Put(start, value)
}
func (this *MyCalendarThree) Book(start int, end int) int {
this.Add(start, 1)
this.Add(end, -1)
maxBook, r := 0, 0
for it := this.Iterator(); it.Next(); {
maxBook += it.Value().(int)
if maxBook > r {
r = maxBook
}
}
return r
}class MyCalendarThree { // array + ksort 实现
private $treeMap = array();
function __construct() {
}
function book($start, $end) {
$this->treeMap[$start] += 1;
$this->treeMap[$end] -= 1;
$maxBook = $r = 0;
ksort($this->treeMap);
foreach ($this->treeMap as $book) {
$maxBook += $book;
$r = max($maxBook, $r);
}
return $r;
}
}class MyCalendarThree {
private TreeMap<Integer, Integer> treeMap;
public MyCalendarThree() {
treeMap = new TreeMap<Integer, Integer>();
}
public int book(int start, int end) {
treeMap.put(start, treeMap.getOrDefault(start, 0) + 1);
treeMap.put(end, treeMap.getOrDefault(end, 0) - 1);
int maxBook = 0;
int r = 0;
for (int key : treeMap.keySet()) {
maxBook += treeMap.get(key);
r = Math.max(r, maxBook);
}
return r;
}
}from sortedcontainers import SortedDict # sortedcontainers 实现
class MyCalendarThree:
def __init__(self):
self.treeMap = SortedDict()
def book(self, start: int, end: int) -> int:
self.treeMap[start] = self.treeMap.get(start, 0) + 1
self.treeMap[end] = self.treeMap.get(end, 0) - 1
maxBook, r = 0, 0
for book in self.treeMap.values():
maxBook += book
r = max(r, maxBook)
return r