区间问题

# 56. 合并区间 (opens new window)

class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        res.add(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            int[] pre = res.getLast();
            int[] cur = intervals[i];
            if(cur[0]<=pre[1]){
                pre[1] = Math.max(cur[1],pre[1]);
            }else{
                res.add(cur);
            }
        }
        return res.toArray(new int[0][0]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 57. 插入区间 (opens new window)

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length+1][2];
        int idx=0,i=0;
        while(i<intervals.length && intervals[i][1]<newInterval[0]){
            res[idx++] = intervals[i++];
        }
        while(i<intervals.length && intervals[i][0]<=newInterval[1]){
            newInterval[0] = Math.min(intervals[i][0],newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1],newInterval[1]);
            i++;
        }
        res[idx++] = newInterval;
        while(i<intervals.length){
            res[idx++] = intervals[i++];
        }
        return Arrays.copyOf(res,idx);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 435. 无重叠区间 (opens new window)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            return a[1]-b[1];
        });
        int cnt = 0;
        int bound = Integer.MIN_VALUE;
        for(int i=0;i<intervals.length;i++){
            if(bound<=intervals[i][0]){
                bound = intervals[i][1];
            }else{
                cnt++;
            }
        }
        return cnt;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 452. 用最少数量的箭引爆气球 (opens new window)

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 不能使用lambda排序，a[1]-b[1]出现越界，重写compare方法
        // [[-2147483646,-2147483645],[2147483646,2147483647]]
        Arrays.sort(points,(a,b)->{
            return a[1]<b[1]?-1:1;
        });
        int ret = 1;
        int pre = points[0][1];
        for(int i=1;i<points.length;i++){
            if(points[i][0]>pre){
                ret++;
                pre = points[i][1];
            }
        }
        return ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 406. 根据身高重建队列 (opens new window)

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 1.先排队
        // 按第一个元素降序，第二个元素升序
        Arrays.sort(people,(a,b)->{
            if(a[0]==b[0]){
                return a[1]-b[1];
            }
            return b[0]-a[0];
        });
        List<int[]> que = new ArrayList<>();
        // 2.插队
        for(int[] p:people){
            que.add(p[1],p);
        }
        return que.toArray(new int[people.length][2]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

← 二维数组摩尔投票法→