435. 無(wú)重疊區(qū)間

435. 無(wú)重疊區(qū)間 - 力扣（LeetCode）
本題和射氣球題目類似，都是重疊區(qū)間問(wèn)題，先按照左區(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ū)間問(wèn)題，當(dāng)沒(méi)有區(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]);
    }
}