Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 to t must be <= r*t (bandwith limit).


Given n = 3, (b1,t1)=(2000,1), (b2, t2)=(6000,2), (b3,t3)=(2000,1) and r = 5000

The sequence 1,2,3 is valid.

There is any algorithm for checking if given n, r and the n packets, it exists a valid sequence in O(n) ??


  • $\begingroup$ I think that exists a solution iff for each packet i, we have that b(i) < r * t(i) $\endgroup$ – Shurhand Apr 12 '18 at 21:26
  • 1
    $\begingroup$ What have you tried so far? You tagged this with dynamic programming and greedy algorithms. Have you tried applying those algorithm design paradigms? What progress have you made? What candidate greedy algorithms have you tested, and do they appear to work? What decomposition into subproblems have you considered for dynamic programming, and where do you run into difficulty? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Apr 13 '18 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.