Google – Find a Path Among Circles

Google – Find a Path Among Circles
有一个通道，在y坐标0到1之间：
y = 1 —————————–
y = 0 —————————–
然后input一堆Circles，每个Circles有三个值，x, y, r, 分别表示圆心和半径。问题是在这条通道里是否能找出一条路径，可以从x的负无穷到正无穷。
路径不一定要直线，可以随便弯弯曲曲，但是如果有一个或者多个circle完全block了通道，就没有路径。
[Mistake]
一开始以为就是道Merge Interval的题目，合并每个圆的纵向interval, [y – r, y + r]，一旦发现超过[0, 1]范围就返回false.
但是后来发现不是这样的：
比如一个圆在x = 0处，纵向interval为[0.5， 1.5]，
另一个圆在x = 10000处，反正就是离的非常远，然后纵向interval为[-0.5, 0.9]
如果merge的话，肯定是超过[0, 1]范围，但是依然可以找出一条满足要求的路径。
所以这道题merge interval是有条件的，只有当两个圆相交或者相切，才能merge它们的纵向interval。
[Solution]
其实说白了就是cluster circles。只要有一个cluster的纵向interval超过范围了，就返回false。
Merge Intervals的变形，只有相交或者相切才merge，需要O( n² ) time，因为每处理一个circle，都要和之前处理过的所有circle判断是否相交。
注意不能通过单纯通过sort x来判断是否相交，sort后第i个圆甚至可能出现和第i – 2个圆相交，但是和i – 1的圆没有半毛钱关系的情况。所以暂时没有想到比quadratic time更好的解法。
另外相交相切的条件：

圆心距离 < r1 + r2 相交
圆心距离 = r1 + r2 相切
圆心距离 > r1 + r2 相离

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;

    }

  }

}

Read full article from Google – Find a Path Among Circles