Google – Search in Interval
input一堆intervals, 有叠加，给一个值，查询在不在这堆intervals里。（查询会调用很多次）
Follow up是查询有多少个intervals包含这个值，也一样会调用很多次。
[Solution]
__[Solution #1]__
Interval Tree
constructor: buildtree O(nlogn)
queryExist O(logn)
queryNumber O(n)
__[Solution #2]__
Scan-Line
constructor: sort O(nlogn)
queryExist O(logn)
queryNumber O(logn)
思路就是把interval变成两条Line，根据坐标排序，从左到右扫一遍，碰到start就cnt++，碰到end就cnt–。每条Line存当前的cnt。
那么query的时候就用binary search找idx的ceiling，找到之后要分情况考虑:
Read full article from Google – Search in Interval
input一堆intervals, 有叠加，给一个值，查询在不在这堆intervals里。（查询会调用很多次）
Follow up是查询有多少个intervals包含这个值，也一样会调用很多次。
[Solution]
__[Solution #1]__
Interval Tree
constructor: buildtree O(nlogn)
queryExist O(logn)
queryNumber O(n)
__[Solution #2]__
Scan-Line
constructor: sort O(nlogn)
queryExist O(logn)
queryNumber O(logn)
思路就是把interval变成两条Line，根据坐标排序，从左到右扫一遍，碰到start就cnt++，碰到end就cnt–。每条Line存当前的cnt。
那么query的时候就用binary search找idx的ceiling，找到之后要分情况考虑:
- if ceilling = 0，return 0
- else if ceiling – 1 是end, 并且ceiling – 1正好等于idx，那要返回ceiling-1的cnt+1
- else 直接返回ceiling – 1的cnt
class Interval { int start; int end; Interval(int start, int end) { this.start = start; this.end = end; }}// interval tree solutionclass Solution { TLine root; public Solution(Interval[] intervals) { this.root = new TLine(intervals[0].start, intervals[0].end); for (int i = 1; i < intervals.length; i++) { insert(root, intervals[i]); } } private TLine insert(TLine curr, Interval interval) { if (curr == null) { return new TLine(interval.start, interval.end); } if (interval.start < curr.l) { curr.left = insert(curr.left, interval); } else { curr.right = insert(curr.right, interval); } if (curr.left != null) { curr.maxValue = Math.max(curr.maxValue, curr.left.maxValue); } if (curr.right != null) { curr.maxValue = Math.max(curr.maxValue, curr.right.maxValue); } return curr; } // still O(n) time public int query(int idx) { return dfs(root, idx); } private int dfs(TLine curr, int idx) { if (curr == null) { return 0; } int result = 0; if (curr.l <= idx && curr.r >= idx) { result = 1; } if (curr.left != null && idx <= curr.left.maxValue) { return result + dfs(curr.left, idx) + dfs(curr.right, idx); } else { return result + dfs(curr.right, idx); } } private class TLine { int l; int r; int maxValue; TLine left; TLine right; TLine(int l, int r) { this.l = l; this.r = r; this.maxValue = r; } }}// scan-line algorithmclass Solution2 { List<Line> list = new ArrayList<>(); public Solution2(Interval[] intervals) { for (Interval interval : intervals) { list.add(new Line(interval.start, true)); list.add(new Line(interval.end, false)); } Collections.sort(list, new Comparator<Line>() { public int compare(Line a, Line b) { if (a.x == b.x) { return a.isStart? -1 : 1; } return a.x - b.x; } }); int cnt = 0; for (int i = 0; i < list.size(); i++) { if (list.get(i).isStart) { cnt++; } else { cnt--; } list.get(i).cnt = cnt; } } public int query(int idx) { int ceil = findCeil(idx, 0, list.size() - 1); if (ceil == 0) { return 0; } if (!list.get(ceil - 1).isStart && list.get(ceil - 1).x == idx) { return list.get(ceil - 1).cnt + 1; } return list.get(ceil - 1).cnt; } private int findCeil(int idx, int l, int r) { if (idx < list.get(l).x) { return l; } if (list.get(r).x <= idx) { return r + 1; } int mid = l + (r - l) / 2; if (list.get(mid).x <= idx) { if (mid != r && list.get(mid + 1).x > idx) { return mid + 1; } else { return findCeil(idx, mid + 1, r); } } else { if (mid != l && list.get(mid - 1).x <= idx) { return mid; } else { return findCeil(idx, l, mid - 1); } } } private class Line { int x; boolean isStart; int cnt = 0; Line(int x, boolean isStart) { this.x = x; this.isStart = isStart; } }}