数组
双指针
排序
题目描述
给定两个人的空闲时间表:slots1
和 slots2
,以及会议的预计持续时间 duration
,请你为他们安排 时间段最早 且 合适的会议时间。
如果没有满足要求的会议时间,就请返回一个 空数组 。
「空闲时间」的格式是 [start, end]
,由开始时间 start
和结束时间 end
组成,表示从 start
开始,到 end
结束。
题目保证数据有效:同一个人的空闲时间不会出现交叠的情况,也就是说,对于同一个人的两个空闲时间 [start1, end1]
和 [start2, end2]
,要么 start1 > end2
,要么 start2 > end1
。
示例 1:
输入: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
输出: [60,68]
示例 2:
输入: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
输出: []
提示:
1 <= slots1.length, slots2.length <= 104
slots1[i].length, slots2[i].length == 2
slots1[i][0] < slots1[i][1]
slots2[i][0] < slots2[i][1]
0 <= slots1[i][j], slots2[i][j] <= 109
1 <= duration <= 106
解法
方法一:排序 + 双指针
我们可以将两个人的空闲时间分别排序,然后使用双指针遍历两个数组,找到两个人的空闲时间段的交集,如果交集的长度大于等于 duration
,则返回交集的起始时间和起始时间加上 duration
。
时间复杂度 $O(m \times \log m + n \times \log n)$,空间复杂度 $O(\log m + \log n)$。其中 $m$ 和 $n$ 分别为两个数组的长度。
Python3 Java C++ Go Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution :
def minAvailableDuration (
self , slots1 : List [ List [ int ]], slots2 : List [ List [ int ]], duration : int
) -> List [ int ]:
slots1 . sort ()
slots2 . sort ()
m , n = len ( slots1 ), len ( slots2 )
i = j = 0
while i < m and j < n :
start = max ( slots1 [ i ][ 0 ], slots2 [ j ][ 0 ])
end = min ( slots1 [ i ][ 1 ], slots2 [ j ][ 1 ])
if end - start >= duration :
return [ start , start + duration ]
if slots1 [ i ][ 1 ] < slots2 [ j ][ 1 ]:
i += 1
else :
j += 1
return []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public List < Integer > minAvailableDuration ( int [][] slots1 , int [][] slots2 , int duration ) {
Arrays . sort ( slots1 , ( a , b ) -> a [ 0 ] - b [ 0 ] );
Arrays . sort ( slots2 , ( a , b ) -> a [ 0 ] - b [ 0 ] );
int m = slots1 . length , n = slots2 . length ;
int i = 0 , j = 0 ;
while ( i < m && j < n ) {
int start = Math . max ( slots1 [ i ][ 0 ] , slots2 [ j ][ 0 ] );
int end = Math . min ( slots1 [ i ][ 1 ] , slots2 [ j ][ 1 ] );
if ( end - start >= duration ) {
return Arrays . asList ( start , start + duration );
}
if ( slots1 [ i ][ 1 ] < slots2 [ j ][ 1 ] ) {
++ i ;
} else {
++ j ;
}
}
return Collections . emptyList ();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public :
vector < int > minAvailableDuration ( vector < vector < int >>& slots1 , vector < vector < int >>& slots2 , int duration ) {
sort ( slots1 . begin (), slots1 . end ());
sort ( slots2 . begin (), slots2 . end ());
int m = slots1 . size (), n = slots2 . size ();
int i = 0 , j = 0 ;
while ( i < m && j < n ) {
int start = max ( slots1 [ i ][ 0 ], slots2 [ j ][ 0 ]);
int end = min ( slots1 [ i ][ 1 ], slots2 [ j ][ 1 ]);
if ( end - start >= duration ) {
return { start , start + duration };
}
if ( slots1 [ i ][ 1 ] < slots2 [ j ][ 1 ]) {
++ i ;
} else {
++ j ;
}
}
return {};
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 func minAvailableDuration ( slots1 [][] int , slots2 [][] int , duration int ) [] int {
sort . Slice ( slots1 , func ( i , j int ) bool { return slots1 [ i ][ 0 ] < slots1 [ j ][ 0 ] })
sort . Slice ( slots2 , func ( i , j int ) bool { return slots2 [ i ][ 0 ] < slots2 [ j ][ 0 ] })
i , j , m , n := 0 , 0 , len ( slots1 ), len ( slots2 )
for i < m && j < n {
start := max ( slots1 [ i ][ 0 ], slots2 [ j ][ 0 ])
end := min ( slots1 [ i ][ 1 ], slots2 [ j ][ 1 ])
if end - start >= duration {
return [] int { start , start + duration }
}
if slots1 [ i ][ 1 ] < slots2 [ j ][ 1 ] {
i ++
} else {
j ++
}
}
return [] int {}
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45 impl Solution {
#[allow(dead_code)]
pub fn min_available_duration (
slots1 : Vec < Vec < i32 >> ,
slots2 : Vec < Vec < i32 >> ,
duration : i32
) -> Vec < i32 > {
let mut slots1 = slots1 ;
let mut slots2 = slots2 ;
// First sort the two vectors based on the beginning time
slots1 . sort_by ( | lhs , rhs | { lhs [ 0 ]. cmp ( & rhs [ 0 ]) });
slots2 . sort_by ( | lhs , rhs | { lhs [ 0 ]. cmp ( & rhs [ 0 ]) });
// Then traverse the two vector
let mut i : usize = 0 ;
let mut j : usize = 0 ;
let N = slots1 . len ();
let M = slots2 . len ();
while i < N && j < M {
let ( start , end ) = ( slots1 [ i ][ 0 ], slots1 [ i ][ 1 ]);
while j < M && slots2 [ j ][ 0 ] < end {
// If still in the scope
let ( cur_x , cur_y ) = (
std :: cmp :: max ( start , slots2 [ j ][ 0 ]),
std :: cmp :: min ( end , slots2 [ j ][ 1 ]),
);
if cur_y - cur_x >= duration {
return vec! [ cur_x , cur_x + duration ];
}
// Otherwise, keep iterating
if slots1 [ i ][ 1 ] < slots2 [ j ][ 1 ] {
// Update i then
break ;
}
j += 1 ;
}
i += 1 ;
}
// The default is an empty vector
vec! []
}
}