一组学生分组的算法设计

Question

我正在学习算法设计，我看到了这个问题:问题:我们有n个学生(编号从1到n)。学生需要分组进行课堂活动。每个学生在他们的小组中有多少学生有自己的偏好。具体来说，学生i希望他们组中的学生数量介于xi和yi之间。换句话说，如果这个组(我被分配到的那个学生)有G个人，那么xi≤G≤yi必须保持。每个学生都必须分配到一个组中(即使组中只有一个学生)。给定n和x[]，y[]的算法应该确定这是否可能。

下面是一些示例：

例1: n= 5，(x[]，y[]) ={ (1，2)，(1，3)，(2，3)，(2，2)，(3，3)}。

我们可以将学生1和学生4分配到一个组(此组的大小为2)，并将其他三个学生分配到另一个组。这将满足每个人的约束。

例2: n= 5，(x[]，y[]) ={ (1，2)，(1，2)，(2，3)，(2，2)，(3，3)}。

满足学生5的约束是不可能的，因为只有两个学生对大小为3的组是"OK“的(然而学生5只想在组中有3个学生)。

例3: n= 5，(x[]，y[]) ={ (1，1)，(2，2)，(2，2)，(2，5)，(2，4)}。

可以将学生1分配到单人组。学生2-5可以被任意分配到两个大小为2的小组(因为每个人都可以在他们的小组中有2个学生)。因此，存在许多解决方案。

我的第一个想法是按照yi对数组进行排序，然后从第一个元素开始，根据yi的值将人员分组。但是在示例2的情况下会发生什么呢？

我的第二个想法是按照xi+yi对数组进行排序，因为yi大于xi，所以我们可以从第一个元素开始，并将人员分组(但我认为第一个想法更好)

Answer 1

我认为您的第一个解决方案很好，示例2没有任何问题。

，

1. ，当然，你先按yi对数组排序。然后你从最大的到最小的开始。
2. 如果一个组不能以这种大小创建-你要确保它可以移动到一个更小的大小(例如，没有一个组的“严格”条件只有一种可能的大小)。例如，在情况2中-这是不可能的，因为学生5没有这个选项，所以算法将立即返回False。

Answer 2

我找到了这个问题的多项式解决方案，主要基于对偏好有多大限制的条件进行排序。

注意几件事：

1. 如果某人有一个像[x, x] =>这样的偏好，这是最严格的，因为我们应该给他找一个大小正好相反的组，松散偏好大小的for ex. [1, 1000] =>是限制最少的，直到更严格的偏好是松散的，才需要考虑形成组，一旦达到最大大小，就假设这个组已经形成；例如，=>

代码准备:：class=Group

在实现时，我认为如果我创建一个Group class来维护它会容易得多：

确定该组的所有成员(成员)的最小大小为group

• consolidated group

• validity-checker-method的最大大小，以确定该组最终是否有效。例如，[(3, 3), (2, 3)] 不是valid-group

如何从初始偏好列表开始

如上所述，我们需要根据限制性最强到限制性最低的偏好(即y[i]-x[i] )对偏好列表进行排序

时间复杂度: O(N^2)

以下是Python中的工作代码：

from typing import List

class Group:
    def __init__(self, s: int, e: int):
        self.members = [(s, e)]
        self.min, self.max = s, e

    def add_member(self, s: int, e: int):
        self.members.append((s, e))
        self.min, self.max = max(self.min, s), min(self.max, e)

    def can_fit(self, s: int, e: int) -> bool:
        return not (self.reached_maxsize() or (e < self.min or s > self.max))

    def reached_maxsize(self) -> bool:
        return len(self.members) == self.max

    def check_group_validity(self) -> bool:
        num_members = len(self.members)
        return self.min <= num_members <= self.max


def create_groups(preference_list):
    groups: List[Group] = []
    preference_list = sorted(preference_list, key=lambda x: (x[1] - x[0], x[0], x[1]))

    for pref in preference_list:
        found_group = False
        for grp in groups:
            if grp.can_fit(pref[0], pref[1]):
                grp.add_member(pref[0], pref[1])
                found_group = True
                break
        if not found_group:
            groups.append(Group(pref[0], pref[1]))

    # check groups-validity
    if all(group.check_group_validity() for group in groups):
        return groups

    print("No grouping is possible")
    return []


res = create_groups([(1, 2), (1, 3), (2, 3), (2, 2), (3, 3)])
print([x.members for x in res])

res = create_groups([(1, 2), (1, 2), (2, 3), (2, 2), (3, 3)])
print([x.members for x in res])

res = create_groups([(1, 1), (2, 2), (2, 2), (2, 5), (2, 4)])
print([x.members for x in res])

测试输出：

[[(2, 2), (1, 2)], [(3, 3), (2, 3), (1, 3)]]

No grouping is possible
[]

[[(1, 1)], [(2, 2), (2, 2)], [(2, 4), (2, 5)]]