Description

给定$n$个区间$[l{o}_i,h{i}_i]$，求最长不重叠区间个数

Constraints

• $1\le n\le 1000$
• $-1000\le l{o}_i<h{i}_i\le 1000$

Solution

解释同435

Code

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        ranges::sort(pairs, [](auto &a, auto &b) {
            return a[1] < b[1];
        });
        int ans = 0;
        int rmost = -1005;
        for(auto &p : pairs) {
            if(rmost < p[0]) {
                rmost = p[1];
                ans++;
            }
        }
        return ans;
    }
};

Link

LeetCode-646 Maximum Length of Pair Chain