请教随机分配的算法问题

Question

现在有一些电影票，座位号不一定连续。有和座位数相等的人群，现在要随机分配座位给这些人，要求带家属的尽量坐在一起，其他随意。请问是否有现成的算法可以满足这种需求？或者类似的也可以。

Answer 1

囧 这不叫随机算法 你的问题抽象了就是：有N个大小为1..K的区间，有M个大小为1..P的填充物，能不能找到一种方案全部填充。

先将M个填充物按照大小排序：M1....Mm(M1 > M2 ..)。 然后将N个区间排序：N1...Nk（N1<N2...)。然后依次从M中选一个，遍历区间，找到最好小区间可以放下物体，然后更新这个区间的大小，重新排序。

复杂度是 MN^2LOGN。

Answer 2

一个简单的思路是贪心+随机爬山法：

首先贪心，从家族人数从大到小，按优先满足人数多的顺序塞进去得到一个解。

然后不断随机交换解中的两个元素。如果交换后更优，则接受。如果交换后不够优，则以一个接受的概率接受。让这个随即交换过程跑一会儿。

对付实际需求，以及对付提交答案型的算法竞赛问题大概够了。