logo
Redian新闻
>未名空间
>EB23 - 劳工卡
>
求助：递485一定要通过公司律师吗？
avatar
求助：递485一定要通过公司律师吗？# EB23 - 劳工卡
d*i
1 楼
人品比较好，就出了一道题。
n个人，每个人有m个时间段，每个时间段代表这个人是忙碌的
例如：
A： （1， 2）， （7， 9）
B： （1， 3）， （4， 5）
C: （12， 15）
D： （16， 20）
每个人的时间段都是排好序的(时间段是inclusive的， 抱歉没说清楚)。
输出：时间段的集合，在这个时间段里，有人是忙碌的。
上面例子中的输出就应该是：{（1， 5）， （7， 9）， （12， 20）}
思路merge k sorted linked list
Enjoy~
avatar
l*n
2 楼
终于current了。
今天预约了周五的体检，说报告一周左右可以拿到，这个是快还是慢？
然后给公司律师写信，不拽我，打电话去，说最早可以约到的appointment得下周四。
我觉得太晚了，怕来不及下个月第一天及时递。
可以要求公司换律师吗？或者可以不通过律师，自己DIY吗？
avatar
l*a
3 楼
就出一道说明你做的慢吧？

}

【在 d******i 的大作中提到】
: 人品比较好，就出了一道题。
: n个人，每个人有m个时间段，每个时间段代表这个人是忙碌的
: 例如：
: A： （1， 2）， （7， 9）
: B： （1， 3）， （4， 5）
: C: （12， 15）
: D： （16， 20）
: 每个人的时间段都是排好序的(时间段是inclusive的， 抱歉没说清楚)。
: 输出：时间段的集合，在这个时间段里，有人是忙碌的。
: 上面例子中的输出就应该是：{（1， 5）， （7， 9）， （12， 20）}
avatar
F*u
4 楼
你有I-140批准件或者复印件么？

【在 l********n 的大作中提到】
: 终于current了。
: 今天预约了周五的体检，说报告一周左右可以拿到，这个是快还是慢？
: 然后给公司律师写信，不拽我，打电话去，说最早可以约到的appointment得下周四。
: 我觉得太晚了，怕来不及下个月第一天及时递。
: 可以要求公司换律师吗？或者可以不通过律师，自己DIY吗？
avatar
h*o
5 楼
没怎么懂。。。
是merge interval? 还是merge K linked list啊？

}

【在 d******i 的大作中提到】
: 人品比较好，就出了一道题。
: n个人，每个人有m个时间段，每个时间段代表这个人是忙碌的
: 例如：
: A： （1， 2）， （7， 9）
: B： （1， 3）， （4， 5）
: C: （12， 15）
: D： （16， 20）
: 每个人的时间段都是排好序的(时间段是inclusive的， 抱歉没说清楚)。
: 输出：时间段的集合，在这个时间段里，有人是忙碌的。
: 上面例子中的输出就应该是：{（1， 5）， （7， 9）， （12， 20）}
avatar
l*n
6 楼

好像没有，都是直接公司和律师弄得之前，全部的东西。

【在 F*********u 的大作中提到】
: 你有I-140批准件或者复印件么？
avatar
d*i
7 楼

有可能！哈哈
您对google onsite有什么意见和建议吗？
虽然面上google难度很大， 但还是想争取下。

【在 l*****a 的大作中提到】
: 就出一道说明你做的慢吧？
:
: }
avatar
l*n
8 楼

当时就是律师打电话来跟我说140过了。这样子。。。

【在 F*********u 的大作中提到】
: 你有I-140批准件或者复印件么？
avatar
d*i
9 楼

看看leetcode上的merge k sorted list吧，跟那个差不多

【在 h*********o 的大作中提到】
: 没怎么懂。。。
: 是merge interval? 还是merge K linked list啊？
:
: }
avatar
f*d
10 楼
赞~
avatar
k*8
11 楼
赞啊 bless bless~
狗电面。。。我还以为啥呢～～ 哈哈
avatar
y*n
12 楼
用java写了一下，切磋一下哈
main:
// a[0] = （1， 2）-> （7， 9）
// a[1] = （1， 3) -> （4， 5）
// a[2] = （12， 15）
// a[3] = （15， 20）
Interval[] intervals = new Interval[4];
intervals[0] = new Interval(1, 2);
intervals[0].next = new Interval(7, 9);
intervals[1] = new Interval(1, 3);
intervals[1].next = new Interval(4, 5);
intervals[2] = new Interval(12, 15);
intervals[3] = new Interval(15, 20);
Interval result = getUnifiedIntervals(intervals);
public static Interval getUnifiedIntervals(Interval[] intervals) {
for (Interval i : intervals) {
if (i == null) {
// error out
return null;
}
}
// heapify: Make it a heap: Trickling Down in Place: start at node n
/2-1, the rightmost node with children
// O(n/2*log(n))
for (int i = (intervals.length / 2 - 1); i >= 0; i--)
trickleDown(intervals, i, intervals.length);

int heapSize = intervals.length; // size of the heap
// remove min from heap: better refactor to a heap class
Interval result = intervals[0];
intervals[0] = intervals[0].next;
result.next = null;

if (intervals[0] == null) { // empty list found, remove current list
from heap
removeHeapRoot(intervals, heapSize--);
if (heapSize == 0) {
return result;
}
}
else {
trickleDown(intervals, 0, heapSize); // heap root is changed to
intervals[0].next
}


while (result.next == null) { // still only one node
// merge resultCur and root of the heap (current)
Interval current = intervals[0];
intervals[0] = intervals[0].next;
current.next = null;

result = mergeTwoIntervals(result, current);

if (intervals[0] == null) { // empty list found, remove current
list from heap
removeHeapRoot(intervals, heapSize--);
if (heapSize == 0) {
return result;
}
}
else {
trickleDown(intervals, 0, heapSize); // heap root is changed
to intervals[0].next
}
}
// result.next != null -> two nodes
Interval resultPre = result;
Interval resultCur = result.next;

while (true) {
// merge resultCur and root of the heap (current)
Interval current = intervals[0];
intervals[0] = intervals[0].next;
current.next = null;

resultCur = mergeTwoIntervals(resultCur, current);
resultPre.next = resultCur;

if (intervals[0] == null) { // empty list found, remove current
list from heap
removeHeapRoot(intervals, heapSize--);
if (heapSize == 0) {
return result;
}
}
else {
trickleDown(intervals, 0, heapSize); // heap root is changed
to intervals[0].next
}
if (resultCur.next != null) { // two nodes
resultPre = resultCur;
resultCur = resultCur.next;
}
}
}
/**
* @param a input array
* @param i targeted ith element in array to trickledown
* @param size the size of the heap, not size of the array
*/
// just use start of interval and min heap instead
private static void trickleDown(Interval[] a, int i, int size) {
// size = a.length
// the last element is a[size-1] and its parent is a[size/2-1]
while (i < size / 2) {
int leftChild = 2 * i + 1;
int rightChild = leftChild + 1;
int smallerChild;
if (rightChild < size // rightChild exists?
&& a[leftChild].start > a[rightChild].start)
smallerChild = rightChild;
else
smallerChild = leftChild;
if (a[i].start <= a[smallerChild].start)
break;
swap(a, i, smallerChild);
i = smallerChild;
}
}
/**
* remove the first element in heap array, i.e. the max for maxheap or
min for minheap
* @param heapArray input array
* @param size the size of the heap, not size of the array
*/
private static Interval removeHeapRoot(Interval[] heapArray, int size){
Interval root = heapArray[0];
heapArray[0] = heapArray[--size]; // last element is heapArray[size
- 1]
trickleDown(heapArray, 0, size);
return root;
}
/**
* Merge Interval a, Interval b
* @param a
* @param b
* @return either one interval or two intervals
*/
private static Interval mergeTwoIntervals(Interval a, Interval b) {
if (a.start > b.start) {
return mergeTwoIntervals(b, a);
}

// a.start <= b.start
if (b.start <= a.end) {
return new Interval(a.start, b.end); // merge to one
}

a.next = b;
return a; // return two nodes
}

}

【在 d******i 的大作中提到】
: 人品比较好，就出了一道题。
: n个人，每个人有m个时间段，每个时间段代表这个人是忙碌的
: 例如：
: A： （1， 2）， （7， 9）
: B： （1， 3）， （4， 5）
: C: （12， 15）
: D： （16， 20）
: 每个人的时间段都是排好序的(时间段是inclusive的， 抱歉没说清楚)。
: 输出：时间段的集合，在这个时间段里，有人是忙碌的。
: 上面例子中的输出就应该是：{（1， 5）， （7， 9）， （12， 20）}
avatar
c*a
13 楼
是不是merge interval啊?
avatar
d*i
14 楼

是， 就是merge interval啊

【在 c*****a 的大作中提到】
: 是不是merge interval啊?
avatar
d*i
15 楼

This is my solution I got during the interview.
Suppose there are N lists. and the longest list has M intervals.
There are two similar solutions.
one gives (M*N)log(M*N), the other one gives (M*N)log(M);
I wrote down the first solution, cus codes are simpler than the second one,:
D. and later I discussed about the second one with the interviewer.
The first one is a straightforward one.
put all of the intervals into one minHeap.
Each time get the top of the heap, and decide if it could be merged with the
previous interval.
A. if true, merge.
B. else, put the previous interval into result list, and use the current
interval as previous interval.
The second one has the similar idea.
Instead of storing all of the intervals, only stores the head of each list
into the minHeap. each time we pop of an interval, we add its next interval
into the heap(if !NULL).
In this way, we have maintain a heap of size N instead of M*N.
This solution is better in Big O, but the code may be a little longer. :D

【在 y****n 的大作中提到】
: 用java写了一下，切磋一下哈
: main:
: // a[0] = （1， 2）-> （7， 9）
: // a[1] = （1， 3) -> （4， 5）
: // a[2] = （12， 15）
: // a[3] = （15， 20）
: Interval[] intervals = new Interval[4];
: intervals[0] = new Interval(1, 2);
: intervals[0].next = new Interval(7, 9);
: intervals[1] = new Interval(1, 3);
avatar
d*i
16 楼

好牛，写的丝丝入扣，不过应该可以直接用现成的数据结构吧，不用麻烦自己写，而且
时间也不允许。

【在 y****n 的大作中提到】
: 用java写了一下，切磋一下哈
: main:
: // a[0] = （1， 2）-> （7， 9）
: // a[1] = （1， 3) -> （4， 5）
: // a[2] = （12， 15）
: // a[3] = （15， 20）
: Interval[] intervals = new Interval[4];
: intervals[0] = new Interval(1, 2);
: intervals[0].next = new Interval(7, 9);
: intervals[1] = new Interval(1, 3);
avatar
s*x
17 楼
你没法用heap这样的数据结构吧。priorityqueue 不open 需要的api吧。

【在 d******i 的大作中提到】
:
: 好牛，写的丝丝入扣，不过应该可以直接用现成的数据结构吧，不用麻烦自己写，而且
: 时间也不允许。
avatar
s*x
18 楼
extra space is needed that way.
the above solution does not require additional space and same running time

,:
the

【在 d******i 的大作中提到】
:
: 好牛，写的丝丝入扣，不过应该可以直接用现成的数据结构吧，不用麻烦自己写，而且
: 时间也不允许。
avatar
d*i
19 楼

c++中 priority_queue, CompareFunc> que.
这样不可以吗，。

【在 s********x 的大作中提到】
: 你没法用heap这样的数据结构吧。priorityqueue 不open 需要的api吧。
avatar
F*9
20 楼
楼主有误吧。
应该是 heap 找极值。
不是merge sort吧。

}

【在 d******i 的大作中提到】
: 人品比较好，就出了一道题。
: n个人，每个人有m个时间段，每个时间段代表这个人是忙碌的
: 例如：
: A： （1， 2）， （7， 9）
: B： （1， 3）， （4， 5）
: C: （12， 15）
: D： （16， 20）
: 每个人的时间段都是排好序的(时间段是inclusive的， 抱歉没说清楚)。
: 输出：时间段的集合，在这个时间段里，有人是忙碌的。
: 上面例子中的输出就应该是：{（1， 5）， （7， 9）， （12， 20）}
avatar
l*b
21 楼
两两合并，分而治之，因为是链表应该不需要额外空间吧。
如果可以用额外空间写成递归可能很简单
avatar
s*x
22 楼
楼上那样的root value of heap 变了，没法trickledown吧用priorityqueue

【在 d******i 的大作中提到】
:
: c++中 priority_queue, CompareFunc> que.
: 这样不可以吗，。
avatar
c*u
23 楼
（15,16）有人忙碌吗? 怎么就（12,20）都有人忙碌了？

}

【在 d******i 的大作中提到】
: 人品比较好，就出了一道题。
: n个人，每个人有m个时间段，每个时间段代表这个人是忙碌的
: 例如：
: A： （1， 2）， （7， 9）
: B： （1， 3）， （4， 5）
: C: （12， 15）
: D： （16， 20）
: 每个人的时间段都是排好序的(时间段是inclusive的， 抱歉没说清楚)。
: 输出：时间段的集合，在这个时间段里，有人是忙碌的。
: 上面例子中的输出就应该是：{（1， 5）， （7， 9）， （12， 20）}
avatar
d*i
24 楼
inclusive 的
avatar
b*p
25 楼
c# 写了一个。。
public List mergeintervals(List> a)
{
List r = new List();
int k = a.Count;
if (k == 0)
return r;
PriorityQueue h = new PriorityQueue();
for (int i = 0; i < k; i++)
{
if (a[i].Count>0)
{
h.Enqueue(a[i][0]);
}
}
Interval currentintval=null;
while (h.Count()>0)
{
if (currentintval == null)
{
currentintval = h.Dequeue();
if (currentintval.next != null)
h.Enqueue(currentintval.next);
}
else
{
Interval minint = h.Dequeue();
if (minint.low > currentintval.high)
{
r.Add(currentintval);
currentintval = minint;
}
else
{
currentintval.low = Math.Min(currentintval.low,
minint.low);
currentintval.high = Math.Max(currentintval.high,
minint.high);
}
if (minint.next != null)
h.Enqueue(minint.next);
}
}
if (currentintval != null)
r.Add(currentintval);
return r;
}
}
avatar
l*b
26 楼
#include
using namespace std;
struct IntNode {
int a;
int b;
IntNode *next;
IntNode(int low, int high) : a(low), b(high), next(NULL) {}
};
struct HeadsNode {
IntNode *list;
HeadsNode *next;
HeadsNode() : next(NULL) {}
};
class MergeInt {
public:
void merger(HeadsNode *h, HeadsNode *t) {
if(h == t) return;
HeadsNode *mid = middle(h,t);
merger(h, mid);
merger(mid->next, t);
h->list = mergeTwoList(h->list, (mid->next)->list);
h->next = t->next;
}
IntNode * mergeTwoList(IntNode *l1, IntNode *l2) {
IntNode *r;
IntNode **h = &r;
while(l1 != NULL && l2 != NULL) {
if(l1->b < l2->a){
*h = l1;
l1 = l1->next;
h = &(*h)->next;
} else if(l2->b < l1->a) {
*h = l2;
l2 = l2->next;
h = &(*h)->next;
} else if(l1->b > l2->b) {
l1->a = min(l1->a, l2->a);
l2 = l2->next;
} else {
l2->a = min(l1->a, l2->a);
l1 = l1->next;
}
}
if(l1 == NULL)
*h = l2;
else
*h = l1;
return r;
}
HeadsNode *middle(HeadsNode *h, HeadsNode *t) {
HeadsNode *p1 = h, *p2 = h->next;
while(p2 != t) {
p1 = p1->next;
p2 = p2->next;
if(p2 != t)
p2 = p2->next;
else
break;
}
return p1;
}
void printInts(IntNode *h) {
while(h!= NULL){
cout << h->a << ", " << h->b << " ";
h = h->next;
}
cout << '\n';
}
};
int main() {
HeadsNode A[4];
for(int i = 0; i < 4 - 1; ++i) {
A[i].next = A + i + 1;
}
IntNode **t = &(A[0].list);
*t = new IntNode(1,2);
t = &(*t)->next;
*t = new IntNode(7,9);
t = &(*t)->next;
*t = new IntNode(10,13);
t = &(A[1].list);
*t = new IntNode(1,3);
t = &(*t)->next;
*t = new IntNode(4,5);
t = &(A[2].list);
*t = new IntNode(8,12);
t = &(A[3].list);
*t = new IntNode(16,20);
MergeInt pp;
pp.merger(A, A+3);
pp.printInts(A[0].list);
return 0;
}
avatar
l*b
27 楼
merger和mergeTwoList
是有用的，其他都是包装
相关阅读
转H4 撤销申请后收到RFEeb2和eb3双140应该怎么办请问我这是不是快了，留给结婚的时间不多了？2012/11的EB2有必要降级么?我9天前网上做的SR这个星期六得到了这样的神回复，也太敷衍我了吧！！！等绿卡过程中升职，怎么处理请问现在的H4 EAD 多久批啊，virginia的应该是在Dallas, TX center批吧###特别急问### EAD/AP Combo 卡入境需要ESTA吗~~~????????????EB2 的I-140刚刚被批准，可以在File一个Eb3的I-140吗我来报绿，pd2012/6，rd2015/6, eb2, nsc【EB3 2016年三月第24绿】（2323PD09/2012--俩人都批了）485 180天后升职换Title有什么注意事项？485 180天后跳槽 取消H1B会激发背景调查吗niw可以降级到eb3 吗？Uscis 账号 被锁有 RD2014 或者以前的同学和我一样在苦等吗？那个J表现在怎么样了？每个月都要有愿意讨论降级的嘛？我现在刚file了 开个微信群取消律师会在case history里面显示吗
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。