## Monday, August 8, 2016

### Google – Find a Path Among Circles

Google – Find a Path Among Circles

y = 1 —————————–
y = 0 —————————–

[Mistake]

[Solution]

Merge Intervals的变形，只有相交或者相切才merge，需要O( n2 ) time，因为每处理一个circle，都要和之前处理过的所有circle判断是否相交。

`class` `Circle {`
`  ``double` `x;`
`  ``double` `y;`
`  ``double` `r;`
`  ``Circle(``double` `x, ``double` `y, ``double` `r) {`
`    ``this``.x = x;`
`    ``this``.y = y;`
`    ``this``.r = r;`
`  ``}`
`}`
`class` `Solution {`
`  ``public` `boolean` `hasPath(Circle[] circles) {`
`    ``if` `(circles == ``null` `|| circles.length == ``0``) {`
`      ``return` `true``;`
`    ``}`
`    ``Map<Circle, Interval> map = ``new` `HashMap<>();`
`    ``map.put(circles[``0``], ``new` `Interval(circles[``0``].y - circles[``0``].r, circles[``0``].y + circles[``0``].r));`
`    ``for` `(``int` `i = ``1``; i < circles.length; i++) {`
`      ``boolean` `hasIntersection = ``false``;`
`      ``Interval newInterval = ``new` `Interval(circles[i].y - circles[i].r, circles[i].y + circles[i].r);`
`      ``for` `(``int` `j = ``0``; j < i; j++) {`
`        ``if` `(isIntersect(circles[j], circles[i])) {`
`          ``merge(map.get(circles[j]), newInterval);`
`          ``if` `(map.get(circles[j]).s <= ``0` `&& map.get(circles[j]).e >= ``1``) {`
`            ``return` `false``;`
`          ``}`
`          ``map.put(circles[i], map.get(circles[j])); `
`          ``hasIntersection = ``true``;`
`        ``}`
`      ``}`
` // maybe first get all intersect intervals and merge them at same time`
` // after for loop, update all intervals to the merged interval`
`      ``if` `(!hasIntersection) {`
`        ``map.put(circles[i], newInterval);`
`      ``}`
`    ``}`
`    ``return` `true``;`
`  ``}`
`  ``private` `boolean` `isIntersect(Circle a, Circle b) {`
`    ``double` `x = Math.abs(a.x - b.x);`
`    ``double` `y = Math.abs(a.y - b.y);`
`    ``double` `len = Math.sqrt(x * x + y * y);`
`    ``return` `len <= a.r + b.r;`
`  ``}`
`  ``// If intersect, there must be an overlap`
`  ``private` `void` `merge(Interval interval, Interval newInterval) {`
`    ``interval.s = Math.min(interval.s, newInterval.s);`
`    ``interval.e = Math.max(interval.e, newInterval.e);`
`  ``}`
`  ``private` `class` `Interval {`
`    ``double` `s;`
`    ``double` `e;`
`    ``Interval(``double` `s, ``double` `e) {`
`      ``this``.s = s;`
`      ``this``.e = e;`
`    ``}`
`  ``}`
`}`