目前我正在阅读Skiena的"算法设计手册"(好了,开始阅读)
他问一个他称之为"电影调度问题"的问题:
问题:电影调度问题
输入:线上n个区间的集合I.
输出:可以从I中选择的相互非重叠区间的最大子集是什么？
示例:(每条虚线都是一部电影,您想要找到电影数量最多的一组)
----a---
-----b---- -----c--- ---d---
-----e--- -------f---
--g-- --h--
我想要解决它的算法是这样的:我可以抛出"最坏的罪犯"(与大多数其他电影相交),直到没有最严重的罪犯(零交叉点).我看到的唯一问题是,如果有一个平局(比如两部不同的电影,每部电影与其他3部电影相交),我扔出哪一部电影是否重要？
基本上我想知道我是如何将这个想法变成"数学"以及如何证明它是正确/不正确的.