算法-区间问题

1
2
3
4
5
6
7
8
9

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        for (int i = 1; i < intervals.length; i++)
            if (intervals[i - 1][1] > intervals[i][0])
                return false;
        return true;
    }
}

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

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[][] ans = new int[intervals.length][2];
        int index = -1;
        for (int[] interval : intervals) {
            if (index == -1 || interval[0] > ans[index][1])
                ans[++index] = interval;
            else
                ans[index][1] = Math.max(ans[index][1], interval[1]);
        }
        return Arrays.copyOf(ans, index + 1);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int[][] merge(int[][] intervals) {
        BitSet bitSet = new BitSet();
        int maxRight = 0;
        for (int[] interval : intervals) {
            // 乘 2 为了使像 [1, 2] 和 [3, 4] 这样的区间不连续
            // [1, 2] -> [2, 4]
            // [3, 4] -> [6, 8]
            int left = interval[0] * 2;
            int right = interval[1] * 2 + 1;
            bitSet.set(left, right); // [left, right)
            maxRight = Math.max(maxRight, right);
        }
        int left = 0;
        int len = 0;
        while (left < maxRight) {
            // [left, right)
            left = bitSet.nextSetBit(left); // 下一个为 1 的位置
            int right = bitSet.nextClearBit(left); // 下一个为 0 的位置
            intervals[len][0] = left / 2;
            intervals[len][1] = right / 2;
            len++;
            left = right;
        }
        return Arrays.copyOf(intervals, len);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        // 1. 在 intervals 中查找最后一个右端点小于 newInterval 左端点的区间
        // 该区间（包含）及之前的区间不用合并
        int left = 0;
        int right = n;
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (intervals[mid][1] < newInterval[0]) left = mid + 1;
            else right = mid;
        }
        // 在 newInterval 之前最后一个不用合并的区间的下标
        int start = right - 1;
        // 2. 在 intervals 中查找第一个左端点大于 newInterval 右端点的区间
        // 该区间（包含）及之后的区间不用合并
        left = 0;
        right = n;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (intervals[mid][0] > newInterval[1]) right = mid;
            else left = mid + 1;
        }
        // 在 newInterval 之后第一个不用合并的区间的下标
        int end = left;
        // 3. 合并区间
        // [start + 1, end - 1] 区间内的区间需要合并成 1 个区间
        int[][] ans = new int[(start + 1) + 1 + (n - end)][2];
        int idx = 0;
        for (int i = 0; i <= start; i++)
            ans[idx++] = intervals[i];
        ans[idx][0] = newInterval[0];
        ans[idx][1] = newInterval[1];
        if (start + 1 < n) // 需要合并
            ans[idx][0] = Math.min(ans[idx][0], intervals[start + 1][0]);
        if (end - 1 >= 0) // 需要合并
            ans[idx][1] = Math.max(ans[idx][1], intervals[end - 1][1]);
        idx++;
        for (int i = end; i < n; i++)
            ans[idx++] = intervals[i];
        return ans;
    }
}

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

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int ans = 0;
        int pre = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[pre][1]) { // 重叠
                if (intervals[i][1] < intervals[pre][1]) pre = i; // 被包含
                ans++;
            } else pre = i; // 不重叠
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class RangeModule {
    TreeMap<Integer, Integer> ranges = new TreeMap<>(); // {l=r}

    public void addRange(int left, int right) {
        Integer ll = ranges.floorKey(left);  // 左侧区间的左端点 ll <= left
        Integer rl = ranges.floorKey(right); // 右侧区间的左端点 rl <= right
        // [ll, lr) 和 [left, right) 区间重叠 ll <= left <= lr (ll < lr)
        if (ll != null && ranges.get(ll) >= left) left = ll;
        // [left, right) 和 [rl, rr) 区间重叠 rl <= right <= rr (rl < rr)
        if (rl != null && ranges.get(rl) >= right) right = ranges.get(rl);
        // 将 [left, right) 向两端扩充为合并后的区间
        ranges.put(left, right);
        // 迭代器删除被 [left, right) 包含的区间
        var it = ranges.keySet().iterator();
        while (it.hasNext()) {
            int l = it.next();
            int r = ranges.get(l);
            if (left < l && r <= right) it.remove();
        }
    }

    public boolean queryRange(int left, int right) {
        Integer ll = ranges.floorKey(left); // 左侧区间的左端点 ll <= left
        // 若 ll <= left < right <= lr，则返回 true
        return ll == null ? false : right <= ranges.get(ll);
    }

    public void removeRange(int left, int right) {
        Integer ll = ranges.lowerKey(left);  // 左侧区间的左端点 ll < left
        Integer rl = ranges.lowerKey(right); // 右侧区间的左端点 rl < right
        if (ll != null) {
            int lr = ranges.get(ll);
            if (lr > right) { // 分割区间 ll < left < right < lr
                ranges.put(ll, left);
                ranges.put(right, lr);
            } else if (lr > left) { // 分割区间 ll < left < lr <= right
                ranges.put(ll, left);
            }
        }
        if (rl != null) {
            int rr = ranges.get(rl);
            // 若 rl < left，则 rl == ll，之前已经分割
            if (rr > right) { // 分割区间 left <= rl < right < rr
                ranges.put(rl, right); // 减小区间，便于删除
                ranges.put(right, rr);
            }
        }
        // 迭代器删除被 [left, right) 包含的区间
        var it = ranges.keySet().iterator();
        while (it.hasNext()) {
            int l = it.next();
            int r = ranges.get(l);
            if (left <= l && r <= right)
                it.remove();
        }
    }
}