Help in a problem:

Правка en5, от _MASTER__, 2023-07-30 16:19:33

The problem: say that we have M tasks that we MUST execute, for each task i you can execute it from Xi to Yi (an interval of hours)

and you must execute each task for a minimum of X hours and X <=(Yi-Xi+1) (those X hours must be contiguous)

input: X, M and (X,Y) for each task.

each cpu can execute at most one task in the same time.

output: give me the minimum number of cpus neeeded an the tasks used by each cpu.

(I got a solution for M<22 and number of hours and X is small like binary search on number of cpus and dp bitmask to check if there is a solution)

complexity is high! how we can do better? for bigger M

feel free to say every idea that you have for any constraint.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский _MASTER__ 2023-07-30 16:30:06 149
en5 Английский _MASTER__ 2023-07-30 16:19:33 47
en4 Английский _MASTER__ 2023-07-30 16:18:30 55
en3 Английский _MASTER__ 2023-07-30 16:15:18 36
en2 Английский _MASTER__ 2023-07-30 16:08:16 119
en1 Английский _MASTER__ 2023-07-30 16:02:44 698 Initial revision (published)