435. 無重疊區(qū)間
題目鏈接/文字講解：無重疊區(qū)間
題設(shè)：給定一個區(qū)間的集合 intervals 抖拦，其中 intervals[i] = [starti, endi] 屡萤。返回 需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊 渊鞋。注意: 可以認為區(qū)間的終點總是大于它的起點。 區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”畔师，但沒有相互重疊范嘱。
思路：按照右邊界排序，從左向右記錄非交叉區(qū)間的個數(shù)瘦癌。最后用區(qū)間總數(shù)減去非交叉區(qū)間的個數(shù)就是需要移除的區(qū)間個數(shù)了，
按照左邊界排序的代碼：
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
int count = 0;
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
if (intervals.length == 0) return 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
count++;
intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);
}
}
return count;
}
}
763.劃分字母區(qū)間
題目鏈接/文字講解：劃分字母區(qū)間
題設(shè)：給你一個字符串 s 跷敬。我們要把這個字符串劃分為盡可能多的片段讯私，同一字母最多出現(xiàn)在一個片段中。
注意，劃分結(jié)果需要滿足：將所有劃分結(jié)果按順序連接妄帘，得到的字符串仍然是 s 楞黄。
返回一個表示每個字符串片段的長度的列表。
思路：要找每一個字母的邊界抡驼，如果找到之前遍歷過的所有字母的最遠邊界鬼廓，說明這個邊界就是分割點了。
可以分為如下兩步：
- 統(tǒng)計每一個字符最后出現(xiàn)的位置
- 從頭遍歷字符致盟，并更新字符的最遠出現(xiàn)下標碎税，如果找到字符最遠出現(xiàn)位置下標和當前下標相等了，則找到了分割點馏锡。
更新區(qū)間時雷蹂，left=i+1,right=max(right,當前字母右邊界)。
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList<>();
int[] edge = new int[26];
for (int i = 0; i < s.length(); i++) {
char letter = s.charAt(i);
edge[letter - 'a'] = i;
}
int left = 0;
int right = 0;
for (int i = 0; i < s.length(); i++) {
char letter = s.charAt(i);
right = Math.max(right, edge[letter - 'a']);
if (right == i) {
list.add(right - left + 1);
left = i + 1;
}
}
return list;
}
}
56. 合并區(qū)間
題目鏈接/文字講解：合并區(qū)間
題設(shè)：以數(shù)組 intervals 表示若干個區(qū)間的集合杯道，其中單個區(qū)間為 intervals[i] = [starti, endi] 匪煌。請你合并所有重疊的區(qū)間，并返回 一個不重疊的區(qū)間數(shù)組党巾，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 萎庭。邊界重合可視為重合區(qū)間。
思路：按照左邊界從小到大排序之后齿拂，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左邊界 <= intervals[i - 1]的右邊界驳规，則一定有重疊。
用合并區(qū)間后左邊界和右邊界署海，作為一個新的區(qū)間吗购，加入到result數(shù)組里就可以了。如果沒有合并就把原區(qū)間加入到result數(shù)組砸狞。
注意捻勉，在遍歷結(jié)束后還要添加一次，否則最后一個區(qū)間不能加入返回的result數(shù)組趾代。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int left = intervals[0][0];
int right = intervals[0][1];
List<int[]> res = new LinkedList<>();
int index;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= right) {
right = Math.max(right, intervals[i][1]);
} else {
res.add(new int[]{left, right});
left = intervals[i][0];
right = intervals[i][1];
}
}
res.add(new int[]{left, right});
return res.toArray(new int[res.size()][]);
}
}
