[C++] Clean Code


  • 4
    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.


  • 0

    @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.


Log in to reply
 

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