//
// Created by 罗炳国 on 2023/7/8.
//

#ifndef PFJ_CODE03_FINDLONGESTCHAIN_H
#define PFJ_CODE03_FINDLONGESTCHAIN_H

#include "commonHeader.h"

/**

 给你一个由n个数对组成的数对数组pairs，其中pairs[i] = [lefti, righti]且lefti< righti 。

现在，我们定义一种 跟随 关系，当且仅当b < c时，数对p2 = [c, d]才可以跟在p1 = [a, b]后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-length-of-pair-chain
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 * */

class code646_findLongestChain {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int N = pairs.size();

        std::sort(pairs.begin(), pairs.end(), [](const vector<int> &a, const vector<int>& b)->bool
            {
                return a[0] < b[0];
            });

        vector<int> ends;
        for (auto &p:pairs) {
            int l = 0, r = ends.size() - 1;
            int target = p[0];
            while (l <= r) {
                int mid = l + ((r - l) >> 1);
                if (ends[mid] >= target)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            if (l == ends.size())
                ends.push_back(p[1]);
            ends[l] = min(p[1], ends[l]);
        }
        return ends.size();
    }

};

#endif //PFJ_CODE03_FINDLONGESTCHAIN_H