## Monday, August 8, 2016

### Google – Search in Interval

input一堆intervals, 有叠加，给一个值，查询在不在这堆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)

1. if ceilling = 0，return 0
2. else if ceiling – 1 是end, 并且ceiling – 1正好等于idx，那要返回ceiling-1的cnt+1
3. else 直接返回ceiling – 1的cnt

`class` `Interval {`
`  ``int` `start;`
`  ``int` `end;`

`  ``Interval(``int` `start, ``int` `end) {`
`    ``this``.start = start;`
`    ``this``.end = end;`
`  ``}`
`}`

`// interval tree solution`
`class` `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 algorithm`
`class` `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;`
`    ``}`
`  ``}`
`}`