435. 無重疊區(qū)間
435. 無重疊區(qū)間 - 力扣（LeetCode）
本題和射氣球題目類似，都是重疊區(qū)間問題风秤，先按照左區(qū)間排序鳖目，如果下一區(qū)間和上一區(qū)間有重疊，那么count+1唁情，同時(shí)取兩者右邊界較小值與后面區(qū)間繼續(xù)比較
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a,b) -> {
return Integer.compare(a[0],b[0]);
});
int count = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= intervals[i-1][1]) {
continue;
} else {
count++;
intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
}
}
return count;
}
}
763.劃分字母區(qū)間
763. 劃分字母區(qū)間 - 力扣（LeetCode）
首先計(jì)算出每個(gè)元素出現(xiàn)的最遠(yuǎn)位置疑苔，然后遍歷字符串甫匹，選擇最大的最遠(yuǎn)位置甸鸟，直到該最大值等于該最遠(yuǎn)位置，就分割區(qū)間
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> result = new ArrayList<>();
//計(jì)算元素的最遠(yuǎn)位置
int[] edge = new int[26];
for (int i = 0; i < s.length(); i++) {
edge[s.charAt(i) - 'a'] = i;
}
int left = 0;
int right = 0;
for (int i = 0; i < s.length(); i++) {
right = Math.max(right, edge[s.charAt(i) - 'a']);
if (i == right) {
result.add(right - left + 1);
left = i + 1;
}
}
return result;
}
}
56. 合并區(qū)間
56. 合并區(qū)間 - 力扣（LeetCode）
本題仍然是區(qū)間問題兵迅，當(dāng)沒有區(qū)間重疊時(shí)抢韭，直接加入數(shù)組中，如果有重疊恍箭，那么合并即可刻恭，合并時(shí)右邊界取較大值
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> result = new LinkedList<>();
Arrays.sort(intervals, (a,b) -> {
return a[0] - b[0];
});
result.add(intervals[0]);
int start;
int end;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= result.getLast()[1]) {
start = result.getLast()[0];
end = Math.max(result.getLast()[1], intervals[i][1]);
result.removeLast();
result.add(new int[]{start, end});
} else {
result.add(intervals[i]);
}
}
return result.toArray(new int[result.size()][2]);
}
}
