0
$\begingroup$

I'm learning algorithm design and I saw this problem: Problem: We have n students in (numbered from 1 to n). Students need to be divided into group for in-class activities. Each student has a preference in terms of how many students are present in their group. Specifically, student i wishes that the number of students in their group is between x[i] and y[i] (inclusive). In other words, if the group (that student i is assigned to) has G people, then x[i] ≤ G ≤ y[i] must hold. Every student must be assigned to a group (even if the group consists only of 1 student). Given n and x[], y[]'s, algorithm should determine whether this is possible or not.

Below are some examples:

Example 1: n = 5, (x[], y[]) = { (1, 2), (1, 3), (2, 3), (2, 2), (3, 3)}.

We can assign student 1 and student 4 to one group (this group's size is 2) and the other three students to another group. This would satisfy everyone's constraint.

Example 2: n = 5, (x[], y[]) = { (1, 2), (1, 2), (2, 3), (2, 2), (3, 3)}.

It is impossible to satisfy student 5's constraint because there are only two students who are "OK" with a group of size 3 (yet student 5 only wants to have exactly 3 students in the group).

Example 3: n = 5, (x[], y[]) = { (1, 1), (2, 2), (2, 2), (2, 5), (2, 4)}.

Student 1 can be assigned to a solo-group. Students 2-5 can be arbitrarily assigned to two groups of size two (as everyone is OK with 2 students in their group). Hence, many solutions exist.

My first idea is to sort the array by y[i] and then starting from the first element, put people in groups depends on the value of y[i]. But what will happen in case of example 2?

My second idea is to sort the array by x[i]+y[i], since y[i] is greater than x[i], we can start from the first element and put people in group ( but i think first idea is better)

Overall, I think these 2 algorithms are not sufficient, I'm looking for something more sufficient (If there is)

$\endgroup$