请教随机分配的算法问题

Question

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

Answer 1

囧这不叫随机算法你的问题抽象了就是：有N个大小为1..K的区间，有M个大小为1..P的填充物，能不能找到一种方案全部填充。
先将M个填充物按照大小排序：M1....Mm(M1>M2..)。然后将N个区间排序：N1...Nk（N1
复杂度是MN^2LOGN。
                            

Answer 2

一个简单的思路是贪心+随机爬山法：
首先贪心，从家族人数从大到小，按优先满足人数多的顺序塞进去得到一个解。
然后不断随机交换解中的两个元素。如果交换后更优，则接受。如果交换后不够优，则以一个接受的概率接受。让这个随即交换过程跑一会儿。
对付实际需求，以及对付提交答案型的算法竞赛问题大概够了。