当前位置:网站首页>力扣今日题-729. 我的日程安排表 I
力扣今日题-729. 我的日程安排表 I
2022-07-06 02:25:00 【抗争的小青年】
729. 我的日程安排表 I
二分
- 先将所有已经预定的序列进行排序,然后依次遍历区间,看某个区间的
left1
,是否大于end
12会和3,5,10进行比较,这是会发现没有比它大的区间,这时就该考虑往它们后面插入了。
- 未找到:那就和最后一个区间的
right1
比较,看最后一个区间的right1是否小于插入区间的start,如果可以就返回ture,否则就返回false
12会和最后一个元素的15进行比较,发现15是大于12的,返回false.
而17先和3,7,10进行比较,发现都比它们大,所以考虑往后面放置,然后20和15比较,发现20大于15,返回true。
- 判断到第一个就找到了
一判断,就发现
end
要小于最小的left1
,所以可以插入,就返回true
- 中间插入
中间区间,找到last的上一个区间pre[left2,right2]
,若right2要大于start,则说明有交集,返回false,否则返回true。
先判断,发现10==10,停下来判断7,一看7<8有交集,返回false。
比如[9,10]这是一个正确的例子,发现 10 =- 10,停下来判断,一看9> 8,返回true。
- 代码:
List<int[]> data;
public MyCalendar() {
data = new ArrayList<>();
}
public boolean book(int start, int end) {
if (data.size() == 0) {
data.add(new int[]{
start, end});
return true;
}
data.sort(Comparator.comparingInt(o -> o[0]));
int left = 0, right = data.size() - 1;
//找到第一个start >= end的区间
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (data.get(mid)[0] >= end) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
//没有找到 和最后一个区间比较
if (ans == -1) {
int[] ints = data.get(data.size() - 1);
if (ints[1] > start) {
return false;
}
} else if (ans != 0) {
//不是第一个区间,如果是第一个区间则可以直接插入
int[] pre = data.get(ans - 1);
if (pre[1] > start) {
return false;
}
}
data.add(new int[]{
start, end});
return true;
}
直接遍历
class MyCalendar {
// 定义一个booked
List<int[]> booked;
public MyCalendar() {
booked = new ArrayList<int[]>();
}
public boolean book(int start, int end) {
for(int[] arr : booked){
int l = arr[0] ,r = arr[1];
//第二种情况
if(l < end && start < r){
return false;
}
}
booked.add(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); */
[s1,e1)和[s2,e2)
,没有交集满足s1>e2
或者s2>e1
,反之则说明两者回产生交集。
思路三
转变一下思维,可以把重叠这个概念扩展到广义的相等概念,即一旦重叠就代表两个元素相等,那么这就简单了,set专门用来去重存储。 那么HashSet和TreeSet用哪个呢? 首先HashSet去重是根据对象的哈希值,由于我们要存储的是int[]类型的,我们在写代码的时候是要根据start和end来创建它,那么它们的哈希值基本不同,也就是说就算两个int[]里面的值完全一样,但是哈希值不同,HashSet也会把它们存进去。 由于我们把重叠看作是广义上的相等,那么就需要定义一个比较器要区分它们的是否广义相等,而TreeSet支持自定义比较器,而且根据比较器返回的值进行排序,非常符合我们的需求。
class MyCalendar {
//定义一个TreeSet
TreeSet<int[]> calendars;
public MyCalendar() {
calendars = new TreeSet<>((a, b) -> {
if(a[1] <= b[0])
return -1;
else if(a[0] >= b[1])
return 1;
else
return 0;
});
}
public boolean book(int start, int end) {
int[] e = new int[]{
start, end};
return calendars.add(e);
}
}
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */
拓展
TreeSet简介:
有序,不可重复,红黑树,基于Treemap实现,自定义排序等特点。
TreeSet 是一个有序的集合,它的作用是提供有序的Set集合。它继承于AbstractSet抽象类,实现了NavigableSet, Cloneable, java.io.Serializable接口。
TreeSet 继承于AbstractSet,所以它是一个Set集合,具有Set的属性和方法。
TreeSet 实现了NavigableSet接口,意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
TreeSet 实现了Cloneable接口,意味着它能被克隆。
TreeSet 实现了java.io.Serializable接口,意味着它支持序列化。
TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式:自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet为基本操作(add、remove 和 contains)提供受保证的 log(n) 时间开销。
另外,TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的
边栏推荐
- Multiple solutions to one problem, asp Net core application startup initialization n schemes [Part 1]
- Advanced technology management - what is the physical, mental and mental strength of managers
- HDU_p1237_简单计算器_stack
- 从顶会论文看2022年推荐系统序列建模的趋势
- Using SA token to solve websocket handshake authentication
- 【coppeliasim】6自由度路径规划
- SSM assembly
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- 2022年版图解网络PDF
- RDD creation method of spark
猜你喜欢
2022 edition illustrated network pdf
Virtual machine network, networking settings, interconnection with host computer, network configuration
The intelligent material transmission system of the 6th National Games of the Blue Bridge Cup
Computer graduation design PHP animation information website
PHP campus financial management system for computer graduation design
技术管理进阶——什么是管理者之体力、脑力、心力
零基础自学STM32-复习篇2——使用结构体封装GPIO寄存器
Minecraft 1.16.5 生化8 模组 2.0版本 故事书+更多枪械
[depth first search] Ji Suan Ke: Betsy's trip
Using SA token to solve websocket handshake authentication
随机推荐
[postgraduate entrance examination English] prepare for 2023, learn list5 words
FTP server, ssh server (super brief)
高数_向量代数_单位向量_向量与坐标轴的夹角
Exness: Mercedes Benz's profits exceed expectations, and it is predicted that there will be a supply chain shortage in 2022
Use image components to slide through photo albums and mobile phone photo album pages
[robot hand eye calibration] eye in hand
【MySQL 15】Could not increase number of max_open_files to more than 10000 (request: 65535)
729. My schedule I / offer II 106 Bipartite graph
How to set an alias inside a bash shell script so that is it visible from the outside?
[untitled] a query SQL execution process in the database
【无标题】数据库中一条查询SQL执行的过程
数据准备工作
RDD conversion operator of spark
ftp上传文件时出现 550 Permission denied,不是用户权限问题
[eight part essay] what is the difference between unrepeatable reading and unreal reading?
技术管理进阶——什么是管理者之体力、脑力、心力
HttpRunnerManager安装(三)-Linux下配置myql数据库&初始化数据
在线怎么生成富文本
Pat grade a 1033 to fill or not to fill
Prepare for the autumn face-to-face test questions