Top 150 · 区间（4 题）

class Solution {
    public List<String> summaryRanges(int[] nums) {
        int i = 0;
        int j = 0;
        List<String> ans = new ArrayList<>();

        while (j < nums.length) {
            while (j + 1 < nums.length && nums[j + 1] == nums[j] + 1) {
                j++;
            }

            String temp;
            if (i == j) {
                temp = Integer.toString(nums[i]);
            } else {
                temp = Integer.toString(nums[i]) 
                     + "->" 
                     + Integer.toString(nums[j]);
            }

            ans.add(temp);

            j++;
            i = j;
        }

        return ans;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        ArrayList<int[]> ans = new ArrayList();
        int n = intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0],o2[0]);
            }
        });

        int[] cur = new int[2];
        cur[0] = intervals[0][0];
        cur[1] = intervals[0][1];

        for (int i = 1; i < n; i++) {
            if(cur[1] >= intervals[i][0]){
                //merge
                cur[1] = Math.max(intervals[i][1],cur[1]);
            }else{
                ans.add(cur);
                cur = new int[2];
                cur[0] = intervals[i][0];
                cur[1] = intervals[i][1];
            }
        }
        ans.add(cur);
        return ans.toArray(new int[ans.size()][]);
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        ArrayList<int[]> ans = new ArrayList();
        int a = newInterval[0];
        int b = newInterval[1];
        int i =0;
        int n = intervals.length;
        boolean flag = true;
        while(i<n){
            if(intervals[i][1]<a){
                ans.add(intervals[i]);
                i++;
            }else if(intervals[i][0]>b){
                if(flag){
                    ans.add(new int[]{a,b});
                    flag = false;
                }
                ans.add(intervals[i]);
                i++;
            }else{
                a = Math.min(a, intervals[i][0]);
                b = Math.max(b, intervals[i][1]);
                i++;
            }
        }
        if(flag){
            ans.add(new int[]{a,b});
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points.length == 1)return 1;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0],o2[0]);
            }
        });
        int ans =1;
        int right = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if(points[i][0] > right){
                ans++;
                right = points[i][1];
            }else{
                right = Math.min(right,points[i][1]);
            }
        }
        return ans;
    }
}