0

I have a problem to solve like this.

there is time interval, and each time interval can do work once. (I called this, 'task')

if there (4, 8), (1, 3), (8, 10), (0, 3), (6, 8) time interval and each interval means (start time, deadline).

this is one case idle time is three (an idle time is between tasks)

enter image description here

But I want to minimize idle time

enter image description here

How to solve these like problem by problem solving? my friend suggests 'dynamic programming' which is one of problem solving technique, I don't know what it is. Please help me, what is dynamic programming and examples by this problem.

Community
  • 1
  • 1
Silvester
  • 2,819
  • 5
  • 22
  • 23
  • 3
    Wikipedia is your friend: http://en.wikipedia.org/wiki/Dynamic_programming – r_31415 Nov 18 '11 at 18:42
  • 2
    LMGTFY: http://en.wikipedia.org/wiki/Dynamic_programming – Regexident Nov 18 '11 at 18:44
  • 1
    Chapter 6 of Algorithms by Dasgupta, Papadimitriou, and Vazirani is a good introduction to DP: http://www.cs.berkeley.edu/~vazirani/algorithms.html – skyuzo Nov 18 '11 at 18:59
  • Do you mean that during each time interval, only one task can be done? In your picture tasks are being done concurrently. – skyuzo Nov 18 '11 at 19:12
  • 1
    [Possible duplicate](http://stackoverflow.com/q/1065433/387852) – Michael McGowan Nov 18 '11 at 19:56
  • possible duplicate of [Good examples, articles, books for understanding dynamic programming](http://stackoverflow.com/questions/4278188/good-examples-articles-books-for-understanding-dynamic-programming) – Saeed Amiri Nov 18 '11 at 22:39

1 Answers1

1

Maybe your friend means to find T1, T2, etc. with idle time in between and try to shorten this? In general dp means to eliminate variables that are unecessary for the solution thus speed up the overall compute time. Here is a good link: difference between back tracking and Dynamic programming

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72