d******i
发帖数: 76 | 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~ | l*****a
发帖数: 14598 | 2 就出一道说明你做的慢吧？
}
【在 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）}
| h*********o
发帖数: 230 | 3 没怎么懂。。。
是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）}
| d******i
发帖数: 76 | 4
有可能！哈哈
您对google onsite有什么意见和建议吗？
虽然面上google难度很大， 但还是想争取下。
【在 l*****a 的大作中提到】
: 就出一道说明你做的慢吧？
:
: }
| d******i
发帖数: 76 | 5
看看leetcode上的merge k sorted list吧，跟那个差不多
【在 h*********o 的大作中提到】
: 没怎么懂。。。
: 是merge interval? 还是merge K linked list啊？
:
: }
| f*********d
发帖数: 140 | | k**8
发帖数: 186 | 7 赞啊 bless bless~
狗电面。。。我还以为啥呢～～ 哈哈 | y****n
发帖数: 192 | 8 用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）}
| c*****a
发帖数: 808 | | d******i
发帖数: 76 | 10
是， 就是merge interval啊
【在 c*****a 的大作中提到】
: 是不是merge interval啊?
| | | d******i
发帖数: 76 | 11
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);
| d******i
发帖数: 76 | 12
好牛，写的丝丝入扣，不过应该可以直接用现成的数据结构吧，不用麻烦自己写，而且
时间也不允许。
【在 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);
| s********x
发帖数: 914 | 13 你没法用heap这样的数据结构吧。priorityqueue 不open 需要的api吧。
【在 d******i 的大作中提到】
:
: 好牛，写的丝丝入扣，不过应该可以直接用现成的数据结构吧，不用麻烦自己写，而且
: 时间也不允许。
| s********x
发帖数: 914 | 14 extra space is needed that way.
the above solution does not require additional space and same running time
,:
the
【在 d******i 的大作中提到】
:
: 好牛，写的丝丝入扣，不过应该可以直接用现成的数据结构吧，不用麻烦自己写，而且
: 时间也不允许。
| d******i
发帖数: 76 | 15
c++中 priority_queue, CompareFunc> que.
这样不可以吗，。
【在 s********x 的大作中提到】
: 你没法用heap这样的数据结构吧。priorityqueue 不open 需要的api吧。
| F********9
发帖数: 44 | 16 楼主有误吧。
应该是 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）}
| l*******b
发帖数: 2586 | 17 两两合并，分而治之，因为是链表应该不需要额外空间吧。
如果可以用额外空间写成递归可能很简单 | s********x
发帖数: 914 | 18 楼上那样的root value of heap 变了，没法trickledown吧用priorityqueue
【在 d******i 的大作中提到】
:
: c++中 priority_queue, CompareFunc> que.
: 这样不可以吗，。
| c*******u
发帖数: 1657 | 19 （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）}
| d******i
发帖数: 76 | | | | b****p
发帖数: 216 | 21 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;
}
} | l*******b
发帖数: 2586 | 22 #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;
} | l*******b
发帖数: 2586 | 23 merger和mergeTwoList
是有用的，其他都是包装 |
|
