当前位置:网站首页>LeetCode 731. 我的日程安排表 II
LeetCode 731. 我的日程安排表 II
2022-07-06 06:02:00 【Sasakihaise_】
【区间拆分与合并】想复杂了,把双次重叠区间给拆分开了,如果进行区间拆分的话要考虑端点相同的情况。
class MyCalendarTwo {
// 双有序集合拆分与合并 1:27 2:47
TreeMap<Integer, Integer> m1 = new TreeMap();
TreeMap<Integer, Integer> m2 = new TreeMap();
public MyCalendarTwo() {
}
public boolean book(int start, int end) {
Integer k2 = m2.lowerKey(end);
if (k2 != null) {
if (m2.get(k2) > start) {
return false;
}
}
Integer key = m1.lowerKey(end);
if (key == null) {
m1.put(start, end);
return true;
}
int value = m1.get(key);
if (value <= start) {
m1.put(start, end);
return true;
}
while (key != null) {
if (m1.get(key) > start) {
value = m1.get(key);
// key start value end 重叠是:max(key, start) min(value, end)
// 左是 min(key, start) max(key, start) 右是 min(value, end) max(value, end)
int l1 = Math.min(key, start);
int e1 = Math.max(key, start);
int l2 = Math.min(value, end);
int e2 = Math.max(value, end);
m2.put(e1, l2);
m1.remove(key);
if (l2 != e2) {
m1.put(l2, e2);
}
if (l1 != e1) {
start = l1;
end = e1;
key = m1.lowerKey(end);
if (key == null) {
m1.put(start, end);
return true;
}
} else {
break;
}
} else {
m1.put(start, end);
break;
}
}
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
【优化】其实一重区间和二重区间有重叠也是没关系的,因为首先就会去二重区间判断。
class MyCalendarTwo {
// 双TreeMap 2:55
TreeMap<Integer, Integer> m1 = new TreeMap();
TreeMap<Integer, Integer> m2 = new TreeMap();
public MyCalendarTwo() {
}
public boolean book(int start, int end) {
Integer k2 = m2.lowerKey(end);
if (k2 != null && m2.get(k2) > start) {
return false;
}
Integer key = m1.lowerKey(end);
while (key != null) {
int value = m1.get(key);
if (value <= start) {
break;
}
m1.remove(key);
m2.put(Math.max(start, key), Math.min(end, value));
start = Math.min(start, key);
end = Math.max(end, value);
key = m1.lowerKey(end);
}
m1.put(start, end);
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
边栏推荐
- 【eolink】PC客户端安装
- 【C语言】qsort函数
- MPLS test report
- CoordinatorLayout+NestedScrollView+RecyclerView 上拉底部显示不全
- VINS-Mono: A Robust and Versatile Monocular Visual-Inertial State Estimator
- Fault, error, failure of functional safety
- LTE CSFB process
- 2022 software testing workflow to know
- Li Chuang EDA learning notes 12: common PCB board layout constraint principles
- Redistemplate common collection instructions opsforvalue (II)
猜你喜欢
C language bubble sort
J'ai un chaton.
[happy Spring Festival] if you feel happy, dance
Web service connector: Servlet
nodejs实现微博第三方登录
Novice entry SCM must understand those things
CoordinatorLayout+NestedScrollView+RecyclerView 上拉底部显示不全
Hypothesis testing learning notes
Expose the serial fraudster Liu Qing in the currency circle, and default hundreds of millions of Cheng Laolai
MPLS test report
随机推荐
【课程笔记】编译原理
H3C防火墙RBM+VRRP 组网配置
Testing and debugging of multithreaded applications
Leetcode 701 insertion operation in binary search tree -- recursive method and iterative method
HCIA复习
Raised a kitten
Wib3.0 leapfrogging, in leapfrogging (ง • ̀_•́) ง
如何在业务代码中使用 ThinkPHP5.1 封装的容器内反射方法
华为路由器忘记密码怎么恢复
查詢生產訂單中某個(些)工作中心對應的標准文本碼
Linux regularly backs up MySQL database
H3C S5820V2_ Upgrade method after stacking IRF2 of 5830v2 switch
H3C S5820V2_5830V2交换机IRF2堆叠后升级方法
GTSAM中李群的運用
Winter 2021 pat class B problem solution (C language)
Embedded point test of app
Significance of unit testing
Report on the competition status and investment decision recommendations of Guangxi hospital industry in China from 2022 to 2028
Hongliao Technology: Liu qiangdong's "heavy hand"
局域网同一个网段通信过程