Maximum Length of Pair Chain解題報告

Description:

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Link:

https://leetcode.com/contest/leetcode-weekly-contest-42/problems/maximum-length-of-pair-chain/

解題方法:

假設(shè)pairs中有元素pairs[min].[1]是整個pairs中最小的奏候,那么這個元素能接上多少元素就是這道題所求的值扭屁。
所以應(yīng)該先把數(shù)組按照每個元素的第二位數(shù)做ascend排序踏堡。
然后再遍歷數(shù)組尋找能接上鏈子的元素,每次找到一個都要更新最小的第二位數(shù)的值。
當(dāng)有兩個元素出現(xiàn)交錯情況比如:(6, 8) 和 (4, 10),因?yàn)槲覀兘?jīng)過了排序,所以能保證當(dāng)有這種交錯元素的時候耕餐,我們總會取到最小的第二位數(shù)也就是8。而剩下的元素(4, 10)并不會進(jìn)入鏈子辟狈。

Time Complexity:

O(NlogN)

完整代碼:

int findLongestChain(vector<vector<int>>& pairs) 
    {
        if(pairs.size() < 2)
            return 0;
        sort(pairs.begin(), pairs.end(), [] (vector<int> a, vector<int> b){
            return a[1] < b[1];
        });
        int len = 1;
        int min = pairs[0][1];
        for(auto a: pairs)
        {
            if(a[0] > min)
            {
                len++; //鏈子長度++
                min = a[1]; //更新
            }
        }
        return len;
    }
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末肠缔,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子上陕,更是在濱河造成了極大的恐慌桩砰,老刑警劉巖拓春,帶你破解...
    沈念sama閱讀 222,464評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件释簿,死亡現(xiàn)場離奇詭異,居然都是意外死亡硼莽,警方通過查閱死者的電腦和手機(jī)庶溶,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,033評論 3 399
  • 文/潘曉璐 我一進(jìn)店門煮纵,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人偏螺,你說我怎么就攤上這事行疏。” “怎么了套像?”我有些...
    開封第一講書人閱讀 169,078評論 0 362
  • 文/不壞的土叔 我叫張陵酿联,是天一觀的道長。 經(jīng)常有香客問我夺巩,道長贞让,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 59,979評論 1 299
  • 正文 為了忘掉前任柳譬,我火速辦了婚禮喳张,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘美澳。我一直安慰自己销部,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,001評論 6 398
  • 文/花漫 我一把揭開白布制跟。 她就那樣靜靜地躺著舅桩,像睡著了一般。 火紅的嫁衣襯著肌膚如雪凫岖。 梳的紋絲不亂的頭發(fā)上江咳,一...
    開封第一講書人閱讀 52,584評論 1 312
  • 那天,我揣著相機(jī)與錄音哥放,去河邊找鬼歼指。 笑死,一個胖子當(dāng)著我的面吹牛甥雕,可吹牛的內(nèi)容都是我干的踩身。 我是一名探鬼主播,決...
    沈念sama閱讀 41,085評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼社露,長吁一口氣:“原來是場噩夢啊……” “哼挟阻!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起峭弟,我...
    開封第一講書人閱讀 40,023評論 0 277
  • 序言:老撾萬榮一對情侶失蹤附鸽,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后瞒瘸,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體坷备,經(jīng)...
    沈念sama閱讀 46,555評論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,626評論 3 342
  • 正文 我和宋清朗相戀三年情臭,在試婚紗的時候發(fā)現(xiàn)自己被綠了省撑。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片赌蔑。...
    茶點(diǎn)故事閱讀 40,769評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖竟秫,靈堂內(nèi)的尸體忽然破棺而出娃惯,到底是詐尸還是另有隱情,我是刑警寧澤肥败,帶...
    沈念sama閱讀 36,439評論 5 351
  • 正文 年R本政府宣布趾浅,位于F島的核電站,受9級特大地震影響馒稍,放射性物質(zhì)發(fā)生泄漏潮孽。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,115評論 3 335
  • 文/蒙蒙 一筷黔、第九天 我趴在偏房一處隱蔽的房頂上張望往史。 院中可真熱鬧,春花似錦佛舱、人聲如沸椎例。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,601評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽订歪。三九已至,卻和暖如春肆捕,著一層夾襖步出監(jiān)牢的瞬間刷晋,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,702評論 1 274
  • 我被黑心中介騙來泰國打工慎陵, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留眼虱,地道東北人。 一個月前我還...
    沈念sama閱讀 49,191評論 3 378
  • 正文 我出身青樓席纽,卻偏偏與公主長得像捏悬,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子润梯,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,781評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)过牙。 張土汪:刷leetcod...
    土汪閱讀 12,748評論 0 33
  • 周國平,初知他的名字源自人教版語文書中有一篇他的文章纺铭,題目是《白兔和月亮》《落難的王子》寇钉,當(dāng)我和學(xué)生一起學(xué)完這篇課...
    靜默草原閱讀 778評論 2 16
  • 編輯部日常工作很忙,而一名同事又休了長假舶赔,于是她之前負(fù)責(zé)的工作很大一部分轉(zhuǎn)移到我手中扫倡,“欲哭無淚”之時琢磨出一些技...
    觀舟閱讀 413評論 1 2
  • 【男人裝】是以男士時尚為主的專題,關(guān)于【男人裝】時尚類的文章均可被收錄顿痪,以下是【男人裝】現(xiàn)有專欄及收錄文章范圍镊辕,供...
    義琳閱讀 1,979評論 6 12
  • 幾天前征懈,某旅游類APP的副總經(jīng)理患心肌梗塞去世的信息出現(xiàn)在小蘇的推送通知中,小蘇不免感覺心痛萬分揩悄。一個四十多歲事業(yè)...
    更好時代閱讀 150評論 0 0