Interval 间隔问题

2018-09-07 09:03:14

一、Merge Intervals

问题描述：

问题求解：

1public List<Interval> merge(List<Interval> intervals) {
2        List<Interval> res = new ArrayList<>();
3        if (intervals.size() == 0) return res;
4        Collections.sort(intervals, new Comparator<Interval>() {
5            public int compare(Interval o1, Interval o2) {
6                return o1.start - o2.start;
7            }
8        });
9        int start = intervals.get(0).start;
10        int end = intervals.get(0).end;
11        for (int i = 1; i < intervals.size(); i++) {
12            if (intervals.get(i).start > end) {
13                res.add(new Interval(start, end));
14                start = intervals.get(i).start;
15                end = intervals.get(i).end;
16            }
17            else {
18                end = Math.max(end, intervals.get(i).end);
19            }
20        }
21        res.add(new Interval(start, end));
22        return res;
23    }

二、Insert Interval

问题描述：

问题求解：

本题的问题描述中明确的说明了，本题的给出条件中的intervals是已经排序好的，并且是没有overlapping的，因此在后续的求解过程中只需要一次遍历即可。

1public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
2        List<Interval> res = new ArrayList<>();
3        int i = 0;
4        while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
5            res.add(intervals.get(i++));
6        }
7        while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
8            newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
9            newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
10            i++;
11        }
12        res.add(newInterval);
13        while (i < intervals.size()) res.add(intervals.get(i++));
14        return res;
15    }

三、My Calendar I

问题描述：

问题求解：

解法一：Boundary Counting

对边界进行计数，最后遍历一遍即可，如果过程中有curSum大于1的情况，则表明出现了overlapping。

如果使用keySet()则会多出log(n)的时间，而本题卡时间非常紧，如果使用key进行提取，则会TLE。

如果使用entrySet()，则会Accept，但是也是将将通过。

public class MyCalendar {   　　TreeMap<Integer, Integer> map;    public MyCalendar() {        map = new TreeMap<>();    }        public boolean book(int start, int end) {        return helper(start, end);    }        private boolean helper(int start, int end) {        map.put(start, map.getOrDefault(start, 0) + 1);        map.put(end, map.getOrDefault(end, 0) - 1);        int curSum = 0;        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {            curSum += entry.getValue();            if (curSum > 1) {                map.put(start, map.get(start) - 1);                if (map.get(start) == 0) map.remove(start);                map.put(end, map.get(end) + 1);                if (map.get(end) == 0) map.remove(end);                return false;            }        }        return true;    }}

解法二、

记录各个interval，并且所有的interval都是没有overlapping的。

1public class MyCalendar {      　　TreeMap<Integer, Integer> treeMap;
2
3    public MyCalendar() {
4        treeMap = new TreeMap<>();
5    }
6
7    public boolean book(int start, int end) {
8        Integer floor = treeMap.floorKey(start);
9        if (floor != null && treeMap.get(floor) > start) return false;
10        Integer ceil = treeMap.ceilingKey(start);
11        if (ceil != null && ceil < end) return false;
12        treeMap.put(start, end);
13        return true;
14    }}

四、My Calendar II

问题描述：

问题求解：

万能的Boundary Counting。

1public class MyCalendarTwo {
2    TreeMap<Integer, Integer> map;
3
4    public MyCalendarTwo() {
5        map = new TreeMap<>();
6    }
7
8    public boolean book(int start, int end) {
9        map.put(start, map.getOrDefault(start, 0) + 1);
10        map.put(end, map.getOrDefault(end, 0) - 1);
11        int cnt = 0;
12        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
13            cnt += entry.getValue();
14            if (cnt > 2) {
15                map.put(start, map.get(start) - 1);
16                if (map.get(start) == 0) map.remove(start);
17                map.put(end, map.get(end) + 1);
18                if (map.get(end) == 0) map.remove(end);
19                return false;
20            }
21        }
22        return true;
23    }
24}

五、My Calendar III

问题描述：

问题求解：

解法一：

万能的Boundary Counting。

1public class MyCalendarThree {
2    TreeMap<Integer, Integer> map;
3
4    public MyCalendarThree() {
5        map = new TreeMap<>();
6    }
7
8    public int book(int start, int end) {
9        map.put(start, map.getOrDefault(start, 0) + 1);
10        map.put(end, map.getOrDefault(end, 0) - 1);
11        int res = 0;
12        int cnt = 0;
13        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
14            cnt += entry.getValue();
15            if (res < cnt) res = cnt;
16        }
17        return res;
18    }
19}

解法二：

线段树求解，效率有较大的提升。

1public class MyCalendarThree {
2    SegmentTree root;
3    int res;
4
5    public MyCalendarThree() {
6        root = new SegmentTree(0, 1000000000, 0);
7        res = 0;
8    }
9
10    public int book(int start, int end) {
11        add(start, end, root);
12        return res;
13    }
14
15    private void add(int start, int end, SegmentTree root) {
16        if (root.m != -1) {
17            if (start >= root.m) add(start, end, root.right);
18            else if (end <= root.m) add(start, end, root.left);
19            else {
20                add(start, root.m, root.left);
21                add(root.m, end, root.right);
22            }
23            return;
24        }
25
26        if (start == root.l && end == root.r) {
27            root.cnt++;
28            res = Math.max(res, root.cnt);
29        }
30        else if (start == root.l) {
31            root.m = end;
32            root.left = new SegmentTree(start, root.m, root.cnt + 1);
33            root.right = new SegmentTree(root.m, root.r, root.cnt);
34            res = Math.max(res, root.cnt + 1);
35        }
36        else if (end == root.r) {
37            root.m = start;
38            root.left = new SegmentTree(root.l, root.m, root.cnt);
39            root.right = new SegmentTree(root.m, root.r, root.cnt + 1);
40            res = Math.max(res, root.cnt + 1);
41        }
42        else {
43            root.m = start;
44            root.left = new SegmentTree(root.l, root.m, root.cnt);
45            root.right = new SegmentTree(root.m, root.r, root.cnt);
46            add(start, end, root.right);
47        }
48    }
49}
50
51class SegmentTree {
52    int l;
53    int r;
54    int m; // m : 分割点，如果尚未分割则为-1。
55    int cnt;
56    SegmentTree left;
57    SegmentTree right;
58
59    SegmentTree(int l, int r, int cnt) {
60        this.l = l;
61        this.r = r;
62        this.m = -1;
63        this.cnt = cnt;
64        this.left = null;
65        this.right = null;
66    }
67}

六、Interval List Intersections

问题描述：

问题求解：

如何快速判断是否相交呢？

1public int[][] intervalIntersection(int[][] A, int[][] B) {
2        List<int[]> res = new ArrayList<>();
3        int i = 0;
4        int j = 0;
5        while (i < A.length && j < B.length) {
6            int s = Math.max(A[i][0], B[j][0]);
7            int e = Math.min(A[i][1], B[j][1]);
8            if (s <= e) res.add(new int[]{s, e});
9            if (A[i][1] < B[j][1]) i++;
10            else j++;
11        }
12        int[][] rst = new int[res.size()][2];
13        for (i = 0; i < res.size(); i++) {
14            rst[i][0] = res.get(i)[0]; 
15            rst[i][1] = res.get(i)[1];
16        }
17        return rst;
18    }