Algorithms: hall allocation (dynamic programming example)

Опубликовано: 04 Январь 2021
на канале: Frank Stajano Explains

949

This video is part of Professor Frank Stajano's lecture course on Algorithms at the University of Cambridge.

One more video with an example of dynamic programming in action. This time the problem is for a sports hall to arrange its schedule so as to allocate the greatest number of activities; or, speaking in more abstract and general terms, given a set of partially overlapping segments on the real axis, to select the largest possible subset of non-overlapping segments. We shall use this particular problem as a bridge between dynamic programming and greedy algorithms, since you may use either approach to solve it.

If you find my lectures useful, give the videos a thumbs up. Subscribe and hit the notification bell for more of the same and to encourage me to publish more videos for budding computer scientists. Leave your comments below.

Course web page:
https://www.cl.cam.ac.uk/teaching/cur...

Course handout:
https://www.cl.cam.ac.uk/teaching/202...

My home page:
https://www.cl.cam.ac.uk/~fms27/