w****k
发帖数: 755 | 1 There are at most eight servers in a data center. Each server has got a
capacity/memory limit. There can be at most 8 tasks that need to be
scheduled on those servers. Each task requires certain capacity/memory to
run, and each server can handle multiple tasks as long as the capacity limit
is not hit. Write a program to see if all of the given tasks can be
scheduled or not on the servers?
Ex:
Servers capacity limits: 8, 16, 8, 32
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
For this example, the program should say 'true'.
Ex2:
Server capacity limits: 1, 3
Task capacity needs: 4
For this example, program should return false. | p*********g
发帖数: 116 | | w****k
发帖数: 755 | 3 Time complexity?
【在 p*********g 的大作中提到】
: DFS？
| m******2
发帖数: 8 | 4 severs limits: max heap (H), size of n // build time O(n)
tasks: sorted list (L) in descending order, size of m // build time O(m
log m)
for each item in L: // O(m)
if H_max >= item_needs:
H_max = H_max - item_needs;
Heapify H_max value in H; // O(log n)
else:
return false;
end if
end for loop
return true;
这样可以不？ | w****k
发帖数: 755 | 5 貌似总是把最大task拿到最大server上去试？这样恐怕不行。
【在 m******2 的大作中提到】
: severs limits: max heap (H), size of n // build time O(n)
: tasks: sorted list (L) in descending order, size of m // build time O(m
: log m)
: for each item in L: // O(m)
: if H_max >= item_needs:
: H_max = H_max - item_needs;
: Heapify H_max value in H; // O(log n)
: else:
: return false;
: end if
| n******n
发帖数: 12088 | 6 装箱问题，NPC
limit
【在 w****k 的大作中提到】
: There are at most eight servers in a data center. Each server has got a
: capacity/memory limit. There can be at most 8 tasks that need to be
: scheduled on those servers. Each task requires certain capacity/memory to
: run, and each server can handle multiple tasks as long as the capacity limit
: is not hit. Write a program to see if all of the given tasks can be
: scheduled or not on the servers?
: Ex:
: Servers capacity limits: 8, 16, 8, 32
: Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
: For this example, the program should say 'true'.
| j**********3
发帖数: 3211 | | l******s
发帖数: 3045 | 8 不是 O(m*n)?
【在 w****k 的大作中提到】
: Time complexity?
| S**********5
发帖数: 896 | |
|
