435. 无重叠区间

435. 无重叠区间 - 力扣（LeetCode）
本题和射气球题目类似，都是重叠区间问题，先按照左区间排序，如果下一区间和上一区间有重叠，那么count+1，同时取两者右边界较小值与后面区间继续比较

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.划分字母区间

763. 划分字母区间 - 力扣（LeetCode）
首先计算出每个元素出现的最远位置，然后遍历字符串，选择最大的最远位置，直到该最大值等于该最远位置，就分割区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        //计算元素的最远位置
        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. 合并区间

56. 合并区间 - 力扣（LeetCode）
本题仍然是区间问题，当没有区间重叠时，直接加入数组中，如果有重叠，那么合并即可，合并时右边界取较大值

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]);
    }
}