算法基础算法

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

字数统计: 2.7k字   |   阅读时长: 12分
,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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