Google 电面

肥宅快乐水

yangdaxian 发表于 2018-6-15 11:13
求大神指点nlogn具体怎么做

不敢.. 还没怎么测试过..

boolean canPass(int[][] rectangles)
{
// sort by x, sort by longer length
Queue<int[]> q = new PriorityQueue<>((a, b) -> (a[0] == b[0] ? b[2] - b[0] : a[2] - a[0]));
for(int[] rec : rectangles) q.offer(rec);
int[] u = null;
while(!q.isEmpty())
{
int[] p = q.poll();
if(u == null) u = p;
if(overlap(u, p))
{
u[0] = Math.min(u[0], p[0]);
u[1] = Math.min(u[1], p[1]);
u[2] = Math.max(u[2], p[2]);
u[3] = Math.max(u[3], p[3]);
if(u[1] <= 0 && u[3] >= 1) return false;
}
else u = p;
}
if(u[1] <= 0 && u[3] >= 1) return false; // for last merged rectangles
return true;
}
boolean overlap(int[] rec1, int[] rec2)
{
int x1 = rec1[0], x2 = rec1[2], y1 = rec1[1], y2 = rec1[3],
x3 = rec2[0], x4 = rec2[2], y3 = rec2[1], y4 = rec2[3];
// either x or y has no intersection
if(x2 < x3 || x4 < x1 || y2 < y3 || y4 < y1) return false;
return true;
}

复制代码

yangdaxian

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

肥宅快乐水

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

yangdaxian

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

肥宅快乐水

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

yangdaxian

kexir123 发表于 2018-6-15 11:53
可以O(nlogn). 我的方法如下
（1）首先遍历长方形，每个长方形保存两个event (x1, y1, y2, true), (x2, y1 ...

能问一下不用线段树，在不merge的情况下如何在logn内判断是否挡住吗？

kexir123

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

yangdaxian

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

kexir123

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

yangdaxian

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式