題目56:intervals[i] = [starti, endi]?。請你合并所有重疊的區(qū)間稠曼,并返回一個不重疊的區(qū)間數(shù)組形病,該數(shù)組需恰好覆蓋輸入中的所有區(qū)間?。
思路:先把區(qū)間按照起點排序霞幅。因為后面我們判斷是否應(yīng)該開啟一個新區(qū)間漠吻,用的判斷語句是?if interval[0] > end,只要后一個區(qū)間起點比現(xiàn)在區(qū)間的終點大司恳,那后面所有區(qū)間的起點就都比現(xiàn)在終點大途乃。因此必然不會和現(xiàn)在區(qū)間重疊。
題目57:無重疊的intervals扔傅,intervals[i] = [starti, endi]耍共。給定一個區(qū)間newInterval = [start, end]。在intervals?中插入?yún)^(qū)間newInterval猎塞,使得intervals按照starti升序排列试读,且區(qū)間之間不重疊(如果有必要的話,可以合并區(qū)間)荠耽。
思路:添加新區(qū)間到intervals钩骇,然后按照起點排序。之后就是合并區(qū)間的邏輯了铝量。
題目435:intervals[i] = [starti, endi]伊履。返回?需要移除區(qū)間的最小數(shù)量,使剩余區(qū)間互不重疊?款违。
思路:先按照終點排序。原因是我們判斷的邏輯是 if intervals[i][0] < end群凶,如果新區(qū)間起點比現(xiàn)在的終點還大插爹,說明這個區(qū)間太大了(排序已經(jīng)保證了后續(xù)區(qū)間的終點大過現(xiàn)有區(qū)間的終點)。那新區(qū)間就該刪除。
題目452:整數(shù)數(shù)組points為氣球的大小赠尾,points[i] = [xstart, xend]表示直徑在xstart和xend之間的氣球力穗。在坐標(biāo)?x?處射出一支箭,若有一個氣球的坐標(biāo)滿足xstart≤ x ≤ xend气嫁,則該氣球會被?引爆当窗。返回引爆所有氣球所必須射出的?最小?弓箭數(shù)。
思路:先按照終點排序寸宵。原因是我們射一支新的箭的邏輯是崖面,沿著第一個區(qū)間的終點射出。如果后續(xù)氣球的起點小于箭頭高度梯影,終點一定大于箭頭高度(因為按照終點排序巫员,后續(xù)區(qū)間的終點一定大于當(dāng)前終點,也就是箭頭)甲棍,必然會被射中简识。反之,如果氣球的起點大于箭頭高度感猛,那需要新射出一支箭七扰。