[C++] Clean Code


  • 10
    1. sort the pairs by their end in increasing order;
    2. at any point, choose the pair that start after the tail end, then use it as the new tail;
    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            sort(pairs.begin(), pairs.end(), cmp);
            int cnt = 0;
            vector<int>& pair = pairs[0];
            for (int i = 0; i < pairs.size(); i++) {
                if (i == 0 || pairs[i][0] > pair[1]) {
                    pair = pairs[i];
                    cnt++;
                }
            }
            return cnt;
        }
    
    private:
        static bool cmp(vector<int>& a, vector<int>&b) {
            return a[1] < b[1] || a[1] == b[1] && a[0] < b[0];
        }
    };
    

    In fact the comparator does not even need to compare the begin:

    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            sort(pairs.begin(), pairs.end(), cmp);
            int cnt = 0;
            for (int i = 0, j = 0; j < pairs.size(); j++) {
                if (j == 0 || pairs[i][1] < pairs[j][0]) {
                    cnt++;
                    i = j;
                }
            }
            return cnt;
        }
    
    private:
        static bool cmp(vector<int>& a, vector<int>&b) {
            return a[1] < b[1];
        }
    };
    

  • 0
    W

    Why does the longest chain always start with the first one in the sorted pairs? I am confused about it.


  • 2

    @Wanhui because you always want to use the pair that end the earlier the better, so that you have more flexibility to use any other pair.


  • 0
    S

    @alexander
    This solution is more clear and better in time complexity, especially comcompared to the current top rated answer "easy dp".
    This one might take O(NlogN) + O(N), while "easy dp" takes O(nlogn) + O(N^2)

    Maybe this is any problem or drawback which havn't identified?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.