文章目录
  1. 1. 题意分析
  2. 2. 代码参考

题意分析

这道题是 leetcode 729 My CalendarI 的翻版,在一的基础上加了重复三次才算失败的条件。这样的话就得用两个 TreeMap 来存储出现一次的区间和出现两次的重叠区间。重叠的情况可能有如下两种情况。

其中对于第二种情况还需要合并重叠区间。对于第一种情况就简单的删除已有的重复区间即可。

代码参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class MyCalendarTwo {

class Interval{
int start;
int end;

Interval(int start , int end){
this.start = start;
this.end = end;
}
}

TreeMap<Integer , Interval> intersection = new TreeMap<>();
TreeMap<Integer , Interval> map = new TreeMap<>();

public MyCalendarTwo() {

}

public boolean book(int start, int end) {
if (checkIntersection(start , end)){
return false;
}
// init map
if (map.size() == 0){
map.put(start , new Interval(start ,end));
return true;
}
// floorkey
Integer floorkey = map.floorKey(start);

if (floorkey != null && map.get(floorkey).end > start){
intersection.put(start , new Interval(start , Math.min(end , map.get(floorkey).end)));
start = map.get(floorkey).start;
end = Math.max(end , map.get(floorkey).end);

map.remove(floorkey);
}

// solve many distance turn into one
Integer ceilingkey = map.ceilingKey(start);
while (ceilingkey != null && ceilingkey < end){
intersection.put(ceilingkey , new Interval(ceilingkey , Math.min(end , map.get(ceilingkey).end)));
end = Math.max(end , map.get(ceilingkey).end);
map.remove(ceilingkey);

ceilingkey = map.ceilingKey(start);
}

map.put(start , new Interval(start , end));

return true;
}

// check intersection
public boolean checkIntersection(int start , int end){
// floorkey
Integer floorkey = intersection.floorKey(start);

if (floorkey != null && intersection.get(floorkey).end > start){
return true;
}

// ceilingkey
Integer ceilingkey = intersection.ceilingKey(start);

if (ceilingkey != null && intersection.get(ceilingkey).start < end)
{
return true;
}

return false;
}
}

/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
文章目录
  1. 1. 题意分析
  2. 2. 代码参考