646. 最长数对链

435. 无重叠区间

（上面两道题类似，都是安排教室使用类的问题，在给定的一些时间间隔中选取不会发生冲突的最大活动安排数量）

  • 动态规划【时间复杂度$O(n^2)$】

    定义 dp[i] 为以pairs[i]（第i项活动） 为结尾的最多能容纳活动的数量

    则在pairs[i][0] > pairs[j][1]，即第i项活动开始晚于第j项活动结束（j<i）的前提下，状态转移方程为dp[i] = max(dp[i], dp[j] + 1);

    要注意

    1. dp数组初始化为全1
    2. 共两层循环，所以时间复杂度$O(n^2)$
    3. 要预先对pairs中的所有活动按照开始时间从早到晚进行排序，这样计算dp[i] 时，所有潜在的dp[j] 已经计算完成
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            int n = pairs.size();
            sort(pairs.begin(), pairs.end());
            vector<int> dp(n, 1);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (pairs[i][0] > pairs[j][1]) {
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp[n - 1];
        }
    };

  • 贪心+二分查找【时间复杂度：$O(n \log n)$】

    改造上面的dp方法，使用二分查找新的活动可以插入的位置，如果满足条件就插入

    同样要求预先对pairs中的所有活动按照开始时间从早到晚进行排序

    用一个数组arr 来记录当前最优情况，arr[i] 就表示长度为 i+1 的数对链的末尾可以取得的最小值，遇到一个新数对时，先用二分查找得到这个数对可以放置的位置，再更新arr。

    代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            sort(pairs.begin(), pairs.end());
            vector<int> arr;
            for (auto p : pairs) {
                int x = p[0], y = p[1];
                if (arr.size() == 0 || x > arr.back()) {
                    arr.emplace_back(y);
                } else {
                    int idx = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
                    arr[idx] = min(arr[idx], y);
                }
            }
            return arr.size();
        }
    };

  • 单纯贪心【时间复杂度：$O(n \log n)$】

    【算法课上讲过这种方法】

    将所有活动按照结束时间从早到晚进行排序，结束时间越早，留给后面活动的时间就越多，应用了贪心的思想

    排序时使用自定义的sort函数，其中记得使用引用传参，减少时间开销

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            int curr = INT_MIN, res = 0;
            sort(pairs.begin(), pairs.end(), [](const vector<int> &a, const vector<int> &b) {
                return a[1] < b[1];
            });
            for (auto &p : pairs) {
                if (curr < p[0]) {
                    curr = p[1];
                    res++;
                }
            }
            return res;
        }
    };