扫描线算法处理一系列区间上的统计问题

  |  

摘要: 扫描线算法、区间列上的统计问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在文章 扫描线算法(Line-Sweep) 中,我们知道在平面上的计算几何问题中,可以通过直线平移扫描的方式,到扫描到位置 x 时如果发生了感兴趣的事件(比如出现了新的矩形),则更新该位置的信息,扫描完成后,得到全局的结果。

这个算法也可以处理一列区间上的统计问题,过程类似,对每个区间端点定义一个事件,同时标记该事件是区间左端点还是右端点,然后将所有事件排序,扫描的过程就是按位置从小到大遍历这些事件,根据要统计的信息,进行相应的更新即可,对于一些复杂问题,简单排序可能不够用,需要平衡树或线段树维护这些 event。

本文看几个直接排序可以处理的问题,看一下用扫描线是如何处理区间列的统计问题的。

题目1:安排会议日程

给定两个人的空闲时间表: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
2
3
4
5
6
1 <= slots1.length, slots2.length <= 1e4
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] <= 1e9
1 <= duration <= 1e6

算法:扫描线算法

给定两列区间 slots1、slots2,每个区间代表空闲时间。我们要找的是 slots1 和 slots2 中各取出一个区间后形成的交集,也就是双方都空闲的时间段,并且要求该时间段大于等于 duration,返回找到的满足要求的开始时间最小的时间段即可。

在扫描的时候记录当前点 x 包含在几个区间中,记为 cnt,由于题目保证数据有效:同一个人的空闲时间不会出现交叠的情况,因此这个值分别为 0, 1, 2。

如果为 0 表示 x 不在任何区间中,如果为 1,表示 x 只在其中一个区间中,如果为 2 则表示 x 分别存在于 slots[0] 中的某区间和 slots[1] 中的某区间中。

代码 (C++)

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
46
47
48
49
50
51
52
53
54
55
56
struct Event
{
int idx;
bool side; // 右: false,左: true;
Event(int idx, bool side):idx(idx),side(side){}
};

struct Cmp
{
bool operator()(const Event& e1, const Event& e2) const
{
if(e1.idx == e2.idx)
return e1.side < e2.side;
return e1.idx < e2.idx;
}
};

class Solution {
public:
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
vector<Event> events;
for(const vector<int>& range: slots1)
{
events.push_back(Event(range[0], true));
events.push_back(Event(range[1], false));
}
for(const vector<int>& range: slots2)
{
events.push_back(Event(range[0], true));
events.push_back(Event(range[1], false));
}
sort(events.begin(), events.end(), Cmp());
int start = 0;
int cnt = 0; // 左端点个数
for(const Event &e: events)
{
if(!e.side)
{
--cnt;
if(cnt == 1)
{
int len = e.idx - start;
if(len >= duration)
return {start, start + duration};
}
}
else
{
++cnt;
if(cnt == 2)
start = e.idx;
}
}
return {};
}
};

题目2:员工空闲时间

给定员工的 schedule 列表,表示每个员工的工作时间。

每个员工都有一个非重叠的时间段 Intervals 列表,这些时间段已经排好序。

返回表示 所有 员工的 共同,正数长度的空闲时间 的有限时间段的列表,同样需要排好序。

注:

1
2
schedule 和 schedule[i] 为长度范围在 [1, 50]的列表。
0 <= schedule[i].start < schedule[i].end <= 10^8。

示例 1:
输入:schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
输出:[[3,4]]
解释:
共有 3 个员工,并且所有共同的
空间时间段是 [-inf, 1], [3, 4], [10, inf]。
我们去除所有包含 inf 的时间段,因为它们不是有限的时间段。

示例 2:
输入:schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
输出:[[5,6],[7,9]]

(尽管我们用 [x, y] 的形式表示 Intervals ,内部的对象是 Intervals 而不是列表或数组。例如,schedule[0][0].start = 1, schedule[0][0].end = 2,并且 schedule[0][0][0] 是未定义的)

而且,答案中不包含 [5, 5] ,因为长度为 0。

算法:扫描线算法

假设有 n 个员工,每个员工有一个区间列,表示员工的工作时间。

我们要找的是这 n 个员工都空闲的区间列。

用扫描线算法处理,将每个区间端点定义一个事件,同时标记是左端点还是右端点,然后将所有事件按照位置排序。然后从左到右扫描。

扫描的过程中记录一个 cnt,表示当前位置属于多少个工作时间区间,遇到左端点时加 1,遇到右端点时减 1。

假设在位置 i 遇到某个右端点,将 cnt 减 1 后变为 0,下一个事件是在位置 j 遇到左端点,则 [i, j] 就是一个我们要找的所有员工都空闲的区间。

代码 (C++)

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Interval {
public:
int start;
int end;

Interval() {}

Interval(int _start, int _end) {
start = _start;
end = _end;
}
};

struct Event
{
int idx;
bool side; // false: 左,true 右
Event(int idx, bool side):idx(idx),side(side){}
};

struct Cmp
{
bool operator()(const Event& e1, const Event& e2) const
{
if(e1.idx == e2.idx)
return e1.side < e2.side;
return e1.idx < e2.idx;
}
};

class Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
int n_person = schedule.size();
vector<Event> events;
for(int i = 0; i < n_person; ++i)
{
vector<Interval> &ranges = schedule[i];
int n_range = ranges.size();
for(int j = 0; j < n_range; ++j)
{
events.push_back(Event(ranges[j].start, false));
events.push_back(Event(ranges[j].end, true));
}
}
sort(events.begin(), events.end(), Cmp());
int n_event = events.size();
int cnt = 0;
vector<Interval> result;
for(int i = 0; i < n_event; ++i)
{
Event e = events[i];
if(e.side)
--cnt;
else
++cnt;
if(cnt == 0)
{
if(i + 1 < n_event)
{
result.push_back(Interval(e.idx, events[i + 1].idx));
}
}
}
return result;
}
};

题目3:会议室 II

给你一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,返回 所需会议室的最小数量 。

示例 1:
输入:intervals = [[0,30],[5,10],[15,20]]
输出:2

示例 2:
输入:intervals = [[7,10],[2,4]]
输出:1

提示:

1
2
1 <= intervals.length <= 1e4
0 <= starti < endi <= 1e6

算法:扫描线算法

本题同样是将每个区间端点定义一个事件,同时记录是左端点还是右端点,然后将所有事件按照位置排序。然后从左到右扫描。

扫描的过程中记录一个 cnt,表示当前位置属于多少个会议时间区间,遇到左端点时加 1,遇到右端点时减 1。

返回过程中 cnt 出现的最大值即为所需会议室数量。

代码 (C++)

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
struct Event
{
int idx;
int kind; // 0左1右
Event(int idx, int kind):idx(idx),kind(kind){}
};

struct Cmp
{
bool operator()(const Event& e1, const Event& e2) const
{
if(e1.idx == e2.idx)
return e1.kind > e2.kind; // 右排前面
return e1.idx < e2.idx;
}
};

class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
int n = intervals.size();
if(n < 2)
return n;
vector<Event> events;
for(int i = 0; i < n; ++i)
{
events.push_back(Event(intervals[i][0], 0));
events.push_back(Event(intervals[i][1], 1));
}
sort(events.begin(), events.end(), Cmp());
int n_event = events.size();
int cnt = 0;
int result = 0;
for(int i = 0; i < n_event; ++i)
{
if(events[i].kind == 0)
++cnt;
if(events[i].kind == 1)
--cnt;
result = max(result, cnt);
}
return result;
}
};

题目4:判断两个事件是否存在冲突

给你两个字符串数组 event1 和 event2 ,表示发生在同一天的两个闭区间时间段事件,其中:

  • event1 = [startTime1, endTime1] 且
  • event2 = [startTime2, endTime2]

事件的时间为有效的 24 小时制且按 HH:MM 格式给出。

当两个事件存在某个非空的交集时(即,某些时刻是两个事件都包含的),则认为出现 冲突 。

如果两个事件之间存在冲突,返回 true ;否则,返回 false 。

提示:

1
2
3
4
5
evnet1.length == event2.length == 2.
event1[i].length == event2[i].length == 5
startTime1 <= endTime1
startTime2 <= endTime2
所有事件的时间都按照 HH:MM 格式给出

示例 1:
输入:event1 = [“01:15”,”02:00”], event2 = [“02:00”,”03:00”]
输出:true
解释:两个事件在 2:00 出现交集。

示例 2:
输入:event1 = [“01:00”,”02:00”], event2 = [“01:20”,”03:00”]
输出:true
解释:两个事件的交集从 01:20 开始,到 02:00 结束。

示例 3:
输入:event1 = [“10:00”,”11:00”], event2 = [“14:00”,”15:00”]
输出:false
解释:两个事件不存在交集。

算法:扫描线算法

首先将 HH:MM 格式的时间改为分钟数的形式,然后将区间端点定义为事件,同时标记是左端点还是右端点,将所有事件排序,然后从左到右扫描。

扫描过程中记录当前位置属于多少个区间,记为 cnt。一旦出现 cnt > 1 的情况,则返回 true。

代码 (C++)

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
46
47
48
49
50
struct Event
{
int idx;
int side; // 0 表示左,1 表示右
Event(){}
Event(int idx, int side):idx(idx),side(side){}
};

struct Cmp
{
bool operator()(const Event& e1, const Event& e2) const
{
if(e1.idx == e2.idx)
return e1.side < e2.side; // 左排前面
return e1.idx < e2.idx;
}
};

class Solution {
public:
bool haveConflict(vector<string>& event1, vector<string>& event2) {
vector<Event> events;
events.push_back(Event(parse(event1[0]), 0));
events.push_back(Event(parse(event1[1]), 1));
events.push_back(Event(parse(event2[0]), 0));
events.push_back(Event(parse(event2[1]), 1));
sort(events.begin(), events.end(), Cmp());
int cnt = 0;
for(const Event &e: events)
{
if(e.side == 0)
cnt++;
else
cnt--;
if(cnt > 1)
return true;
}
return false;
}

int parse(const string& s)
{
int m = 0;
m += (s[0] - '0') * 10 * 60;
m += (s[1] - '0') * 60;
m += (s[3] - '0') * 10;
m += (s[4] - '0');
return m;
}
};

Share