当前位置:网站首页>力扣今日題-729. 我的日程安排錶 I
力扣今日題-729. 我的日程安排錶 I
2022-07-06 02:26: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的
边栏推荐
- Looking at the trend of sequence modeling of recommended systems in 2022 from the top paper
- The third level of C language punch in
- Is there a case where sqlcdc monitors multiple tables and then associates them to sink to another table? All operations in MySQL
- How to set an alias inside a bash shell script so that is it visible from the outside?
- PHP campus movie website system for computer graduation design
- Global and Chinese markets hitting traffic doors 2022-2028: Research Report on technology, participants, trends, market size and share
- 2022 eye health exhibition, vision rehabilitation exhibition, optometry equipment exhibition, eye care products exhibition, eye mask Exhibition
- SQL statement
- RDD conversion operator of spark
- Global and Chinese market of commercial cheese crushers 2022-2028: Research Report on technology, participants, trends, market size and share
猜你喜欢
Black high-end responsive website dream weaving template (adaptive mobile terminal)
High number_ Vector algebra_ Unit vector_ Angle between vector and coordinate axis
A doctor's 22 years in Huawei
Executing two identical SQL statements in the same sqlsession will result in different total numbers
Sword finger offer 29 Print matrix clockwise
2022 China eye Expo, Shandong vision prevention and control exhibition, myopia, China myopia correction Exhibition
MySQL index
PAT甲级 1033 To Fill or Not to Fill
How to generate rich text online
零基础自学STM32-野火——GPIO复习篇——使用绝对地址操作GPIO
随机推荐
Sword finger offer 29 Print matrix clockwise
[Clickhouse] Clickhouse based massive data interactive OLAP analysis scenario practice
剑指 Offer 30. 包含min函数的栈
Data preparation
Xshell 7 Student Edition
Virtual machine network, networking settings, interconnection with host computer, network configuration
论文笔记: 极限多标签学习 GalaXC (暂存, 还没学完)
General process of machine learning training and parameter optimization (discussion)
Paper notes: graph neural network gat
Minecraft 1.16.5 生化8 模组 2.0版本 故事书+更多枪械
Pat grade a 1033 to fill or not to fill
【社区人物志】专访马龙伟:轮子不好用,那就自己造!
729. My schedule I / offer II 106 Bipartite graph
High number_ Vector algebra_ Unit vector_ Angle between vector and coordinate axis
在线怎么生成富文本
Formatting occurs twice when vs code is saved
RDD creation method of spark
Overview of spark RDD
Advanced technology management - what is the physical, mental and mental strength of managers
Number conclusion LC skimming review - 1