「LeetCode」区间覆盖问题(跳跃游戏/灌溉花园/视频拼接等)

2020-04-19
摘要: 本文讨论了一类区间覆盖问题的解法。

问题描述#

给定数轴上的一个大区间 $[0,L]$ 和 n 个小区间 $[l_0,r_0]$, $[l_1,r_1]$, … $[l_{n-1},r_{n-1}]$,,问最少选择多少个小区间,使得这些小区间的并集可以覆盖整个大区间。

基于这个问题的原型,在 LeetCode 上有以下题目:45. 跳跃游戏 II1024. 视频拼接1326. 灌溉花园的最少水龙头数目。另外还有 视野争夺

思路#

贪心法#

我们从左至右考虑,将所有区间按左边界升序”排序“。我们将选择的子区间的个数为 count。针对相同左边界的我们每次选择最长区间(基于贪心思想)。

一开始我们令 count = 0, target = 0, farmost = 0。如图所示,首先我们针对左边界为 $0$ 的区间,选择长度最长的区间,将其右区间记为 target。再继续根据左区间递增的顺序遍历所有子区间,在左区间的值超出 target 前,不断更新我们遇到的最右区间,并将其记为 far-most。若 far-most 大于等于 L,说明已经可以覆盖区间,可以令 count++ 并立即返回。当左区间的值超过 target时,我们断言 far-most 大于 target,否则返回,因为意味着无法满足区间覆盖。同时,我们将 target 设置为 far-most,并将 count++。重复此过程,遍历结束后,我们断言 far-most 大于等于 L,否则意味着无法满足区间覆盖。

简单来说,我们基于贪心的思想,每次选择最长的区间,最终得到的一定是个数最少的方案。实际上,我们并不需要"**排序**"(当然,也可以排序,或者利用 `map` 边记录边排序,或者利用 `unordered_map` 存储)。因为区间长度 `L` 通常是固定的,我们可以直接声明一个大小为 `L` 的数组,并初始化为一个最小值。我们只需要遍历所有提供的子区间,记录 `v[l]` 为以 $l$ 为左区间能到达的最右值。之后再按顺序遍历数组即可(根据 `LeetCode` 提交结果,这样做比排序以及利用 `map`/`unordered_map` 更快更省空间..)。这样做的时间复杂度和空间复杂度都为 $O(n)$。

伪代码如下:

注:为了考虑方便地处理初始化的情况,实际代码逻辑和上述描述有所出入。我们在每次超出 target 时才把上一段纳入计数中。这样并不会使得答案小 $1$,因为当我们找到最后一个区间的时候,那一次循环执行了两次 count++;或者就是不符合题意,返回 $-1$。

if(!v[0]) return -1;
int count = 0, target = 0, farmost = 0;
// 共 n 个区间,它们被存储在 vector<int> v 中。v[i] 代表以 i 为左边界的区间所能达到的最右边界。
for(int i = 0; i <= L; ++i) {
    int p = i, q = v[p];
    if(p > target) {
        // 如果超出目标位置,而最远距离到不了当前节点,则返回 -1
        if(farmost < p) return -1;
        
        // 如果可以走到当前节点,更新目标位置
        target = farmost;
        count++;
    }
    
    farmost = max(farmost, q);
    if(farmost >= L) {
        count++;
        break;
    }
}
if(farmost < L) count = -1;
return count;

例题#

注意,我们每次要设置正确的 Ln 等。

LeetCode 45. 跳跃游戏 II#

45. 跳跃游戏 II

特殊的是如果 n==1,应该直接返回 $0$。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), L = n-1;
        if(n == 1) return 0;
        
        vector<int> v(L+1, -1);
        for(int i = 0; i < n; ++i) {
            v[i] = i + nums[i];
        }

        int  count = 0, target = 0, farmost = 0;
        for(int i = 0; i <= L; ++i) {
            int p = i, q = v[p];
            if(p > target) {
                // 如果超出目标位置,而最远距离到不了当前节点,则返回 -1
                if(farmost < p) return -1;
                
                // 如果可以走到当前节点,更新目标位置
                target = farmost;
                count++;
            }
            
            farmost = max(farmost, q);
            if(farmost >= L) {
                count++;
                break;
            }
        }
        if(farmost < L) return -1;
        return count;
    }
};

LeetCode 1326. 灌溉花园的最少水龙头数目#

1326. 灌溉花园的最少水龙头数目

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<int> v(n+1, -1);
        for(int i = 0; i < n+1; ++i) {
              // 左区间小于 0 应该作为 0
            int p = i-ranges[i] < 0 ? 0 : i - ranges[i], q = i + ranges[i];
            if(q > v[p]) v[p] = q;
        }
        
                //if(v[0] <= 0) return -1;
        
        int L = n, count = 0, target = 0, farmost = 0;
        for(int i = 0; i <= L; ++i) {
            int p = i, q = v[p];
            if(p > target) {
                // 如果超出目标位置,而最远距离到不了当前节点,则返回 -1
                if(farmost < p) return -1;
                
                // 如果可以走到当前节点,更新目标位置
                target = farmost;
                count++;
            }
            
            farmost = max(farmost, q);
            if(farmost >= L) {
                count++;
                break;
            }
        }
        if(farmost < L) count = -1;
        return count;
    }
};

视野争夺 - 腾讯 2020 后台校园招聘试题#

视野争夺 - 腾讯 2020 后台校园招聘试题

由于直接开数组会超出内存,所以采用其他的方式。

vector + 排序#

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp(pair<int, int>& p1, pair<int, int>& p2) {
    return p1.first < p2.first || (p1.first == p2.first && p1.second > p2.second);
}

int main() {
    ios::sync_with_stdio(false);
    
    int n, l;
    cin >> n >> l;
    
    vector<pair<int, int>> v;
    for(int i = 0; i < n; ++i) {
        int p, q;
        cin >> p >> q;
        v.push_back(pair<int,int>(p, q));
    }
    
    sort(v.begin(), v.end(), cmp);
  
    if(v.begin()->first != 0) {
          cout << -1 << endl;
        return 0;
    }
    
    int count = 0, target = 0, farmost = 0;
    for(auto i = v.begin(); i != v.end(); ++i) {
        int p = i->first, q = i->second;
        if(p > target) {
            if(farmost < p) {
                cout << -1 << endl;
                return 0;
            }
            
            target = farmost;
            count++;
        }
        
        farmost = max(farmost, q);
        if(farmost >= l) {
            count++;
            cout << count << endl;
            return 0;
        }
    }
    
    if(farmost < l) count = -1;
    cout << count << endl;
}

map 自动排序#

#include <iostream>
#include <map>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    
    int n, l;
    cin >> n >> l;
    
    map<int, int> m;
    for(int i = 0; i < n; ++i) {
        int p, q;
        cin >> p >> q;
        if(!m.count(p) || m[p] < q) m[p] = q;
    }
  
      if(!m.count(0)) {
          cout << -1 << endl;
        return 0;
    }  
  
    int count = 0, target = 0, farmost = 0;
    for(auto i = m.begin(); i != m.end(); ++i) {
        int p = i->first, q = i->second;
        if(p > target) {
            if(farmost < p) {
                cout << -1 << endl;
                return 0;
            }
            
            target = farmost;
            count++;
        }
        
        farmost = max(farmost, q);
        if(farmost >= l) {
            count++;
            cout << count << endl;
            return 0;
        }
    }
    
    if(farmost < l) count = -1;
    cout << count << endl;
}

1024. 视频拼接#

1024. 视频拼接

由于可能录制超过比赛时长的视频片段(左区间会溢出给定的数组范围),因此应该采用排序的算法,或者丢弃多余的片段。

丢弃多余片段#

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        int n = clips.size(), L = T;
        vector<int> v(L+1, -1);
        for(int i = 0; i < n; ++i) {
            int p = clips[i][0], q = clips[i][1];
              // 丢弃开始时间超过 L 的片段
            if(p <= L && v[p] < q) v[p] = q;
        }

        int count = 0, target = 0, farmost = 0;
        for(int i = 0; i <= L; ++i) {
            int p = i, q = v[p];
            if(p > target) {
                if(farmost < p) return -1;

                target = farmost;
                count++;
            }

            farmost = max(farmost, q);
            if(farmost >= L) {
                count++;
                return count;
            }
        }

        if(farmost < L) return -1;
        return count;
    }
};

vector 排序#

bool cmp(pair<int, int>& p1, pair<int, int>& p2) {
    return p1.first < p2.first || (p1.first == p2.first && p1.second > p2.second);
}

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        int n = clips.size(), L = T;
        vector<pair<int, int>> v;
        for(int i = 0; i < n; ++i) {
            int p = clips[i][0], q = clips[i][1];
            v.push_back(pair<int, int>(p, q));
        }

        sort(v.begin(), v.end(), cmp);

        int count = 0, target = 0, farmost = 0;
        for(auto it = v.begin(); it != v.end(); ++it) {
            int p = it->first, q = it->second;
            if(p > target) {
                if(farmost < p) return -1;

                target = farmost;
                count++;
            }

            farmost = max(farmost, q);
            if(farmost >= L) {
                count++;
                return count;
            }
        }

        if(farmost < L) return -1;
        return count;
    }
};