區(qū)間相關(guān)&用最少數(shù)量的箭引爆氣球

合并區(qū)間

給出一個(gè)區(qū)間的集合照棋，請合并所有重疊的區(qū)間招驴。

示例 1:

輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6]

示例 2:

輸入: [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間

先將元素按照左端點(diǎn)排序
用數(shù)組 merged 存儲最終的答案狞谱。
將第一個(gè)區(qū)間加入 merged 數(shù)組中壳炎，并按順序依次考慮之后的每個(gè)區(qū)間：
如果當(dāng)前區(qū)間的左端點(diǎn)在數(shù)組 merged 中最后一個(gè)區(qū)間的右端點(diǎn)之后哲虾，那么它們不會(huì)重合锦亦，我們可以直接將這個(gè)區(qū)間加入數(shù)組 merged 的末尾茶凳；
否則嫂拴，它們重合，我們需要用當(dāng)前區(qū)間的右端點(diǎn)更新數(shù)組 merged 中最后一個(gè)區(qū)間的右端點(diǎn)贮喧，將其置為二者的較大值筒狠。

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
    int n = 0;
    List<int[]> list = new ArrayList<>();
    for (int[] ints : intervals) {
        if (!list.isEmpty()) {
            int[] interval = list.get(list.size() - 1);
            if (ints[0] <= interval[1]) {
                interval[1] = Math.max(interval[1], ints[1]);
                continue;
            }
        }
        list.add(ints);
    }
    int[][] ans = new int[n][2];
    return list.toArray(ans);
}

時(shí)間復(fù)雜度O(nlogn)

無重疊區(qū)間

給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量箱沦，使剩余區(qū)間互不重疊辩恼。

注意:

  1. 可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。
  2. 區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”谓形，但沒有相互重疊灶伊。

示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊寒跳。

示例 2:

輸入: [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個(gè) [1,2] 來使剩下的區(qū)間沒有重疊聘萨。

示例 3:

輸入: [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因?yàn)樗鼈円呀?jīng)是無重疊的了

方法一：動(dòng)態(tài)規(guī)劃
先按開始時(shí)間排序童太，dp[i]表示前考慮前i個(gè)區(qū)間時(shí)的區(qū)間個(gè)數(shù)（重合的要合并）
最終結(jié)果為初始區(qū)間個(gè)數(shù)-最大區(qū)間個(gè)數(shù)

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals == null || intervals.length <= 1) {
        return 0;
    }
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
    int[] dp = new int[intervals.length];
    Arrays.fill(dp, 1);
    for (int i = 1; i < intervals.length; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (intervals[i][0] >= intervals[j][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return intervals.length - dp[intervals.length - 1];
}

時(shí)間復(fù)雜度O(n2)

方法二：貪心（左邊界排序）
按開始時(shí)間排序米辐，考慮當(dāng)前區(qū)間與前一個(gè)區(qū)間，共三種情況：

  • 不相交书释，下一次考慮的前一個(gè)區(qū)間即為當(dāng)前區(qū)間
  • 前一個(gè)區(qū)間包含了當(dāng)前區(qū)間翘贮，刪除前一個(gè)區(qū)間，下一次考慮的前一個(gè)區(qū)間即為當(dāng)前區(qū)間
  • 前一個(gè)區(qū)間與當(dāng)前區(qū)間部分重疊征冷，刪除當(dāng)前區(qū)間择膝，一次考慮的前一個(gè)區(qū)間不變
public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals == null || intervals.length <= 1) {
        return 0;
    }
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
    int count = 0;
    int[] pre = intervals[0];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < pre[1]) {
            if (pre[1] > intervals[i][1]) {
                pre = intervals[i];
            }
            count++;
            continue;
        } 
        pre = intervals[i];
    }
    return count;
}

時(shí)間復(fù)雜度O(nlogn)

方法三：右邊界排序

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length < 1) {
        return 0;
    }
    Arrays.sort(intervals, (Comparator.comparingInt(o -> o[1])));
    int n = intervals.length;
    int res = 0;
    int right = intervals[0][1];
    for (int i = 1; i < n; i++) {
        if (intervals[i][0] < right) {
            res++;
        } else {
            right = intervals[i][1];
        }
    }
    return res;
}

刪除被覆蓋區(qū)間

給你一個(gè)區(qū)間列表誓琼，請你刪除列表中被其他區(qū)間所覆蓋的區(qū)間检激。
只有當(dāng) c <= a 且 b <= d 時(shí)肴捉，我們才認(rèn)為區(qū)間 [a,b) 被區(qū)間 [c,d) 覆蓋。
在完成所有刪除操作后叔收，請你返回列表中剩余區(qū)間的數(shù)目齿穗。

示例：

輸入：intervals = [[1,4],[3,6],[2,8]]
輸出：2
解釋：區(qū)間 [3,6] 被區(qū)間 [2,8] 覆蓋，所以它被刪除了

待完善的思路：
按照開始時(shí)間排序饺律，如果前一個(gè)區(qū)間覆蓋了當(dāng)前區(qū)間窃页，覆蓋了的區(qū)間個(gè)數(shù)加1，下次考慮的前一個(gè)區(qū)間不變复濒，否則下次考慮的前一個(gè)區(qū)間為當(dāng)前區(qū)間

存在一個(gè)問題：存在開始相同的區(qū)間脖卖，如[[1,2],[1,4],[3,4]]，這種情況要再根據(jù)結(jié)束時(shí)間排序巧颈，后結(jié)束的排在前面

public int removeCoveredIntervals(int[][] intervals) {
    if (intervals.length <= 1) {
        return 1;
    }
    Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0] == 0 ? o2[1] - o1[1]: o1[0] - o2[0]);
    int count = 0;
    int[] pre = intervals[0];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= pre[1]) {
            if (pre[1] >= intervals[i][1]) {
                count++;
                continue;
            }
        }
        pre = intervals[i];
    }
    return intervals.length - count;
}

插入?yún)^(qū)間

給出一個(gè)無重疊的 畦木，按照區(qū)間起始端點(diǎn)排序的區(qū)間列表。
在列表中插入一個(gè)新的區(qū)間砸泛，你需要確保列表中的區(qū)間仍然有序且不重疊（如果有必要的話十籍，可以合并區(qū)間）。

示例 1：

輸入：intervals = [[1,3],[6,9]], newInterval = [2,5]
輸出：[[1,5],[6,9]]

示例 2：

輸入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
輸出：[[1,2],[3,10],[12,16]]
解釋：這是因?yàn)樾碌膮^(qū)間 [4,8] 與 [3,5],[6,7],[8,10] 重疊

方法一：添加+合并區(qū)間
先將新區(qū)間加到數(shù)組中唇礁，利用合并區(qū)間的方式對新數(shù)組進(jìn)行處理

public int[][] insert(int[][] intervals, int[] newInterval) {
    int n = intervals.length;
    int[][] temp = new int[n + 1][2];
    System.arraycopy(intervals, 0, temp, 0, intervals.length);
    temp[n] = newInterval;
    return merge(temp);
}

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
    int n = 0;
    List<int[]> list = new ArrayList<>();
    for (int[] ints : intervals) {
        if (!list.isEmpty()) {
            int[] interval = list.get(list.size() - 1);
            if (ints[0] <= interval[1]) {
                interval[1] = Math.max(interval[1], ints[1]);
                continue;
            }
        }
        list.add(ints);
    }
    int[][] ans = new int[n][2];
    return list.toArray(ans);
}

方法二：
分成三段處理：

  • 結(jié)束時(shí)間比新區(qū)間小勾栗，說明不重疊
  • 合并中間重疊的區(qū)間
  • 開始時(shí)間比新區(qū)間大，說明不重疊
public int[][] insert(int[][] intervals, int[] newInterval) {
    int n = intervals.length;
    int[][] res = new int[n + 1][2];
    int i = 0, j = 0;
    // 將結(jié)束時(shí)間比新區(qū)間開始時(shí)間小的加到結(jié)果集中盏筐，因?yàn)榭隙ú恢丿B
    while (i < n && intervals[i][1] < newInterval[0]) {
        res[j++] = intervals[i++];
    }
    // 處理重疊的區(qū)間
    res[j] = newInterval;
    // 得到最小的開始時(shí)間
    if (i < n && intervals[i][0] < newInterval[0]) {
        res[j][0] = intervals[i][0];
    }
    // 得到最大的結(jié)束時(shí)間
    while (i < n && intervals[i][0] <= newInterval[1]) {
        res[j][1] = Math.max(res[j][1], intervals[i++][1]);
    }
    j++;
    // 之后的區(qū)間是開始時(shí)間比新區(qū)間結(jié)束時(shí)間大围俘，說明不重疊
    while (i < n) {
        res[j++] = intervals[i++];
    }
    // 最終區(qū)間可能沒有n + 1個(gè)
    return Arrays.copyOf(res, j);
}

匯總區(qū)間

給定一個(gè)無重復(fù)元素的有序整數(shù)數(shù)組，返回?cái)?shù)組區(qū)間范圍的匯總琢融。

示例 1:

輸入: [0,1,2,4,5,7]
輸出: ["0->2","4->5","7"]
解釋: 0,1,2 可組成一個(gè)連續(xù)的區(qū)間; 4,5 可組成一個(gè)連續(xù)的區(qū)間

示例 2:

輸入: [0,2,3,4,6,8,9]
輸出: ["0","2->4","6","8->9"]
解釋: 2,3,4 可組成一個(gè)連續(xù)的區(qū)間; 8,9 可組成一個(gè)連續(xù)的區(qū)間

public List<String> summaryRanges(int[] nums) {
    List<String> res = new ArrayList<>();
    int i = 0;
    while (i < nums.length) {
        int j = i + 1;
        while (j < nums.length && nums[j] == nums[j - 1] + 1) {
            j++;
        }
        if (j != i + 1) {
            res.add(nums[i] + "->" + nums[j - 1]);
        } else {
            res.add(String.valueOf(nums[i]));
        }
        i = j;
    }
    return res;
}

763. 劃分字母區(qū)間

字符串 S 由小寫字母組成楷拳。我們要把這個(gè)字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個(gè)片段中吏奸。返回一個(gè)表示每個(gè)字符串片段的長度的列表欢揖。

示例：

輸入：S = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結(jié)果為 "ababcbaca", "defegde", "hijhklij"。
每個(gè)字母最多出現(xiàn)在一個(gè)片段中奋蔚。
像 "ababcbacadefegde", "hijhklij" 的劃分是錯(cuò)誤的她混，因?yàn)閯澐值钠螖?shù)較少。

貪心
由于同一個(gè)字母只能出現(xiàn)在同一個(gè)片段泊碑，顯然同一個(gè)字母的第一次出現(xiàn)的下標(biāo)位置和最后一次出現(xiàn)的下標(biāo)位置必須出現(xiàn)在同一個(gè)片段坤按。因此需要遍歷字符串，得到每個(gè)字母最后一次出現(xiàn)的下標(biāo)位置馒过。

public List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) {
        last[s.charAt(i) - 'a'] = i;
    }
    int start = 0, end = 0;
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);
        if (i == end) {
            res.add(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}

用最少數(shù)量的箭引爆氣球

在二維空間中有許多球形的氣球臭脓。對于每個(gè)氣球，提供的輸入是水平方向上腹忽，氣球直徑的開始和結(jié)束坐標(biāo)来累。由于它是水平的砚作，所以縱坐標(biāo)并不重要，因此只要知道開始和結(jié)束的橫坐標(biāo)就足夠了嘹锁。開始坐標(biāo)總是小于結(jié)束坐標(biāo)葫录。
一支弓箭可以沿著 x 軸從不同點(diǎn)完全垂直地射出。在坐標(biāo) x 處射出一支箭领猾，若有一個(gè)氣球的直徑的開始和結(jié)束坐標(biāo)為 xstart米同，xend， 且滿足 xstart ≤ x ≤ xend摔竿，則該氣球會(huì)被引爆面粮。可以射出的弓箭的數(shù)量沒有限制。 弓箭一旦被射出之后继低，可以無限地前進(jìn)但金。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量郁季。

給你一個(gè)數(shù)組 points 冷溃，其中 points [i] = [xstart,xend] ，返回引爆所有氣球所必須射出的最小弓箭數(shù)梦裂。

示例 1：

輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：對于該樣例似枕，x = 6 可以射爆 [2,8],[1,6] 兩個(gè)氣球，以及 x = 11 射爆另外兩個(gè)氣球

題目意思是：給定n個(gè)閉區(qū)間[x,y]年柠，問最少需要確定多少個(gè)點(diǎn)凿歼，使得每個(gè)閉區(qū)間中都至少存在一個(gè)點(diǎn)。

排序+貪心
按起點(diǎn)排序冗恨，如果有重疊的區(qū)間

public int findMinArrowShots(int[][] points) {
    // 沒有用減法防止溢出
    Arrays.sort(points, (o1, o2) -> {
        if (o1[0] > o2[0]) {
            return 1;
        }
        if (o1[0] < o2[0]) {
            return -1;
        }
        return 0;
    });
    int res = 0;
    int minEnd = Integer.MAX_VALUE;
    // 對每一個(gè)開始的區(qū)間記錄一個(gè)點(diǎn)答憔，然后找能和該區(qū)間重疊的區(qū)間
    for (int i = 0; i < points.length; i++) {
        if (i > 0 && points[i][0] <= minEnd) {
            minEnd = Math.min(minEnd, points[i][1]);
        } else {
            res++;
            minEnd = points[i][1];
        }
    }
    return res;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市掀抹，隨后出現(xiàn)的幾起案子虐拓，更是在濱河造成了極大的恐慌，老刑警劉巖傲武，帶你破解...
    沈念sama閱讀 212,884評論 6贊 492
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件蓉驹，死亡現(xiàn)場離奇詭異，居然都是意外死亡揪利，警方通過查閱死者的電腦和手機(jī)态兴，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,755評論 3贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來疟位，“玉大人瞻润，你說我怎么就攤上這事。” “怎么了绍撞？”我有些...
    開封第一講書人閱讀 158,369評論 0贊 348
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵正勒，是天一觀的道長。 經(jīng)常有香客問我楚午，道長昭齐，這世上最難降的妖魔是什么尿招？ 我笑而不...
    開封第一講書人閱讀 56,799評論 1贊 285
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任矾柜，我火速辦了婚禮，結(jié)果婚禮上就谜，老公的妹妹穿的比我還像新娘怪蔑。我一直安慰自己，他們只是感情好丧荐，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,910評論 6贊 386
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布缆瓣。 她就那樣靜靜地躺著，像睡著了一般虹统。 火紅的嫁衣襯著肌膚如雪弓坞。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 50,096評論 1贊 291
  • 城市分裂傳說
    那天车荔，我揣著相機(jī)與錄音渡冻，去河邊找鬼。 笑死忧便，一個(gè)胖子當(dāng)著我的面吹牛族吻，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播珠增，決...
    沈念sama閱讀 39,159評論 3贊 411
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼超歌，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了蒂教？” 一聲冷哼從身側(cè)響起巍举，我...
    開封第一講書人閱讀 37,917評論 0贊 268
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎凝垛，沒想到半個(gè)月后禀综，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 44,360評論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡苔严，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,673評論 2贊 327
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年定枷，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片届氢。...
    茶點(diǎn)故事閱讀 38,814評論 1贊 341
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡欠窒，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情岖妄，我是刑警寧澤型将，帶...
    沈念sama閱讀 34,509評論 4贊 334
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站荐虐，受9級特大地震影響七兜，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜福扬，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,156評論 3贊 317
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一腕铸、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧铛碑，春花似錦狠裹、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,882評論 0贊 21
  • 一樁弒父案涛菠，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至撇吞，卻和暖如春俗冻，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背牍颈。 一陣腳步聲響...
    開封第一講書人閱讀 32,123評論 1贊 267
  • 情欲美人皮
    我被黑心中介騙來泰國打工迄薄， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人颂砸。 一個(gè)月前我還...
    沈念sama閱讀 46,641評論 2贊 362
  • 代替公主和親
    正文 我出身青樓噪奄，卻偏偏與公主長得像，于是被迫代替她去往敵國和親人乓。 傳聞我的和親對象是個(gè)殘疾皇子勤篮，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,728評論 2贊 351