算法
Source
Edit
History

区间调度问题

一、区间不相交问题

给出N个开区间(start, end)，从中选择尽可能多的区间，使得这些区间两两不相交。

解决思路是将区间集合S中的所有区间按照end值从小到大的顺序进行排序，然后执行下列步骤：

  1. 从区间集合S中选取end值最小的区间i，将i加入区间集合T。
  2. 寻找与i相交的所有区间，将这些区间从集合S中删除。
  3. 若S非空，跳转到步骤1。

区间T即为所求。

证明思路可以考虑反证法：假设某一次选择的i的end值并不是集合S中最小的，如果存在与区间i相交且end值更小的区间i’，则选择i’所移除的区间数不会大于选择i所移除的区间数，此时选取end值更小的i’会使局部结果更优。

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static bool cmp(vector<int>& a, vector<int>& b)
{
    return a[1] < b[1];
}

int mostDisjointIntervals(vector<vector<int>>& intervals)
{
    if (intervals.empty())
        return 0;
    sort(intervals.begin(), intervals.end(), cmp);
    int count = 0;
    int i = 0;
    while (i < intervals.size())
    {
        int j = i + 1;
        // 找到第一个不与intervals[i]相交的区间intervals[j]
        while (j < intervals.size() && intervals[j][0] < intervals[i][1] )
            ++j;
        ++count;
        i = j;
    }

    return count;
}

二、应用1：LeetCode 435 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

移除的最小区间数量就是区间总数减去剩余的最大区间数量。

1
2
3
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    return intervals.size() - mostDisjointIntervals(intervals);
}

三、应用2：LeetCode 452 用最少数量的箭引爆气球

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

在区间不相交问题中，每当选取一个区间时，与其相交的区间也会被移除。这相当于在本问题中，每射爆一个气球，与其相重叠的气球也会被射爆。因此两个问题是等价的，可以套用前面的代码，只不过本题中的区间是闭区间而不是开区间，需要修改边界条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
int mostDisjointIntervals(vector<vector<int>>& intervals)
{
    ...
    while (i < intervals.size())
    {
        ...
        // 将小于号改为小于等于号
        while (j < intervals.size() && intervals[j][0] <= intervals[i][1] )
            ++j;
        ...
    }
    ...
}

四、变形1：LeetCode 56 合并区间

给出一个区间的集合，请合并所有重叠的区间。

本题仍是与区间重叠相关的问题，但是与上面三题有一点不同。上面三题的重叠区间是以某一个区间为参照的，也就是说所有的区间都必须与某一个特定的区间重叠。但是这一题不需要，对于所要合并的区间集合中的每一个区间，只需要与集合中的任意一个区间重叠即可。

本题的算法核心仍是贪心，但是需要做出一点调整：对区间集合使用字典排序，即先比较start，按照start升序排列，若start值相同，再按end升序排列。这样排序的目的是使所有能够进行合并的区间相邻。排序后，从前往后遍历区间，将尽可能多的相邻的重叠区间合并成一个大区间。对于每个合并后的大区间，其start值就是最左侧的小区间的start，其end值是所有小区间当中end值最大的那个。故在遍历期间，需要维护变量maxEnd存储end值的最大值。

题解如下，可见代码在上述三题的基础上修改了比较函数、内层循环的条件以及增加了maxEnd变量的维护：

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
static bool cmp(vector<int>& a, vector<int>& b)
{
    if (a[0] > b[0])
        return false;
    else if (a[0] < b[0])
        return true;
    else if (a[1] < b[1])
        return true;
    return false;
}

vector<vector<int>> merge(vector<vector<int>>& intervals)
{
    vector<vector<int>> ans;
    if (intervals.empty())
        return ans;
    sort(intervals.begin(), intervals.end(), cmp);
    int i = 0;

    while (i < intervals.size())
    {
        int maxEnd = intervals[i][1];
        int j = i + 1;
        // 找到第一个不与intervals[i]相交的区间intervals[j]
        while (j < intervals.size() && intervals[j][0] <= maxEnd)
        {
            if (intervals[j][1] > maxEnd)
            maxEnd = intervals[j][1];
            ++j;
        }  
        ans.push_back(vector<int> {intervals[i][0], maxEnd});
        i = j;
    }

    return ans;
}

五、变形2：LeetCode 57 插入区间

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

这道题的难度为“困难”，但是相比之前的几道题目其实反而不需要用到什么特别的算法，只需从左到右遍历区间集合，找到新区间的插入位置并进行（可能的）合并操作。题目给的区间集合是无重叠的，因此省去了存储maxEnd的步骤，只需考虑边界条件进行适当的分类讨论即可。我的代码较为复杂，还可以进一步简化。

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
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
{
    vector<vector<int>> ans;
    if (intervals.empty())
    {
        ans.push_back(newInterval);
        return ans;
    }

    bool inserted = false;
    int i = 0;
    while (i < intervals.size())
    {
        if (!inserted)
        {
            if (newInterval[0] > intervals[i][1])
                ans.push_back(intervals[i++]);
            else if (newInterval[1] >= intervals[i][0])
            {
                int j = i + 1;
                while (j < intervals.size() && intervals[j][0] <= newInterval[1])
                    ++j;
                int newStart = min(newInterval[0], intervals[i][0]);
                if (j == i + 1)
                    ans.push_back({newStart, max(intervals[i][1], newInterval[1])});
                else
                {
                    ans.push_back({newStart, max(intervals[j - 1][1], newInterval[1])});
                }
                inserted = true;
                i = j;
            }
            else
            {
                ans.push_back(newInterval);
                ans.push_back(intervals[i++]);
                inserted = true;
            }
        }
        else
        {
            ans.push_back(intervals[i++]);
        }
    }
    if (!inserted)
        ans.push_back(newInterval);

    return ans;
}