当前位置:网站首页>LeetCode 731. My schedule II
LeetCode 731. My schedule II
2022-07-06 06:23:00 【Sasakihaise_】
【 Interval splitting and merging 】 I think it's complicated , Split the double overlapping interval , If you want to split an interval, you should consider the same endpoint .
class MyCalendarTwo {
// Splitting and merging of double ordered sets 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 Overlap is :max(key, start) min(value, end)
// Left is min(key, start) max(key, start) On the right is 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);
*/
【 Optimize 】 In fact, it doesn't matter if the primary interval overlaps with the secondary interval , Because first of all, we will go to the double interval judgment .
class MyCalendarTwo {
// double 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);
*/
边栏推荐
- Win10 cannot operate (delete, cut) files
- Left matching principle of joint index
- Avtiviti创建表时报错:Error getting a new connection. Cause: org.apache.commons.dbcp.SQLNestedException
- Isam2 and incrementalfixedlagsmooth instructions in gtsam
- 曼哈顿距离和-打印菱形
- [postman] test script writing and assertion details
- Simulation volume leetcode [general] 1109 Flight reservation statistics
- F - true liars (category and search set +dp)
- MFC dynamically creates dialog boxes and changes the size and position of controls
- Coordinatorlayout+nestedscrollview+recyclerview pull up the bottom display is incomplete
猜你喜欢
调用链监控Zipkin、sleuth搭建与整合
JDBC Requset 对应内容及功能介绍
Full link voltage measurement: building three models
Hypothesis testing learning notes
把el-tree选中的数组转换为数组对象
Postman core function analysis - parameterization and test report
Redis 核心技术与实战之 基本架构:一个键值数据库包含什么?
Black cat takes you to learn EMMC Protocol Part 10: EMMC read and write operation details (read & write)
LeetCode 732. 我的日程安排表 III
记一个基于JEECG-BOOT的比较复杂的增删改功能的实现
随机推荐
Simulation volume leetcode [general] 1061 Arrange the smallest equivalent strings in dictionary order
Simulation volume leetcode [general] 1249 Remove invalid parentheses
MFC on the conversion and display of long string unsigned char and CString
On weak network test of special test
记一个基于JEECG-BOOT的比较复杂的增删改功能的实现
Summary of the post of "Web Test Engineer"
B - The Suspects
【无App Push 通用测试方案
黑猫带你学UFS协议第8篇:UFS初始化详解(Boot Operation)
RestTemplate、Feign实现Token传递
[wechat applet] build a development tool environment
Reading notes of effective managers
全程实现单点登录功能和请求被取消报错“cancelToken“ of undefined的解决方法
Manhattan distance sum - print diamond
数据库隔离级别
模拟卷Leetcode【普通】1219. 黄金矿工
Idea new UI usage
Basic knowledge of error
leetcode 24. Exchange the nodes in the linked list in pairs
MySQL is sorted alphabetically