1. 題目

給出 n 個數(shù)對。 在每一個數(shù)對中，第一個數(shù)字總是比第二個數(shù)字小。

現(xiàn)在，我們定義一種跟隨關(guān)系，當(dāng)且僅當(dāng) b < c 時，數(shù)對(c, d) 才可以跟在 (a, b) 后面。我們用這種形式來構(gòu)造一個數(shù)對鏈。

給定一個對數(shù)集合，找出能夠形成的最長數(shù)對鏈的長度。你不需要用到所有的數(shù)對，你可以以任何順序選擇其中的一些數(shù)對來構(gòu)造。

示例 :輸入: [[1,2], [2,3], [3,4]] 輸出: 2 解釋: 最長的數(shù)對鏈?zhǔn)?[1,2] -> [3,4]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-length-of-pair-chain
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 貪心解題

• 按照結(jié)束位置排序
• 與前面不相交，計數(shù)+1，更新結(jié)束位置為當(dāng)前的結(jié)束位置

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

總結(jié)

以上是生活随笔為你收集整理的LeetCode 646. 最长数对链（区间 贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。