# Algorithm to check if exists a valid streaming sequence in O(n)?

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).

Example:

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) ??

Thanks

• I think that exists a solution iff for each packet i, we have that b(i) < r * t(i) – Shurhand Apr 12 '18 at 21:26
• 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. – D.W. Apr 13 '18 at 4:19