文章目录
  1. 1. 题意描述
  2. 2. 解题思路
  3. 3. 代码参考
  4. 4. 二分搜索解法

题意描述

题的意思大概是持续给你一些 [start,end)的区间,然后让你判断这些区间是否有重叠。
样例:

MyCalendar();

MyCalendar.book(10, 20); // returns true

MyCalendar.book(15, 25); // returns false

MyCalendar.book(20, 30); // returns true

解题思路

这道题可以简单的用遍历的方法来解决。但不采用这种方法。这里需要用到TreeMap这种数据结构。TreeMap是一种基于红黑树实现的经过排序的Map。
这里用到它的floorKey和ceilingKey两个特殊的方法。

  • floorKey(target)方法返回当前Map里小于target的key的最大值。
  • ceilingKey(target)返回当前Map里大于target的key的最小值。

代码参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MyCalendar {
// treemap
TreeMap<Integer , Integer> treemap;
public MyCalendar() {
treemap = new TreeMap<>();
}
public boolean book(int start, int end) {
Integer floorKey = treemap.floorKey(start);
if (floorKey != null && treemap.get(floorKey) > start)
return false;
Integer ceilingKey = treemap.ceilingKey(start);
if (ceilingKey != null && ceilingKey < end) return false;
treemap.put(start , end);
return true;
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/

二分搜索解法

这里还有一种利用二分搜索的解法。这里利用了LinkList的特点,当调用LinkList的add(index , number)的方法的时候,当index重复的时候会发生index偏移。参考代码如下:

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
class MyCalendar {
List<int[]> bookings;
public MyCalendar() {
bookings=new LinkedList<>();
}
public boolean book(int start, int end) {
int s=0, e=bookings.size()-1;
while (s<=e){
int mid=s+(e-s)/2;
int[] bk=bookings.get(mid);
if (bk[0]==start){
return false;
}else if (bk[0]>start){
e=mid-1;
}else{
s=mid+1;
}
}
if (s>0 && start<bookings.get(s-1)[1])
return false;
if (s<bookings.size() && end>bookings.get(s)[0])
return false;
bookings.add(s, new int[]{start, end});
return true;
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/

文章目录
  1. 1. 题意描述
  2. 2. 解题思路
  3. 3. 代码参考
  4. 4. 二分搜索解法