🔗 Gym Clothes

A thief broke in during lunchtime, and some students had their gym clothes stolen. Fortunately, students who brought a spare set of gym clothes are willing to lend them out. Students are numbered by their build, so a student can only lend gym clothes to the student with the number right before or right after them. For example, student 4 can only lend gym clothes to student 3 or student 5. Since a student can't take the class without gym clothes, we need to lend out the gym clothes appropriately so that as many students as possible can attend the gym class.

Given the total number of students n, an array lost containing the numbers of students whose gym clothes were stolen, and an array reserve containing the numbers of students who brought a spare set of gym clothes, write a solution function that returns the maximum number of students who can attend the gym class.

• The total number of students is between 2 and 30.
• The number of students whose gym clothes were stolen is between 1 and n, with no duplicate numbers.
• The number of students who brought a spare set of gym clothes is between 1 and n, with no duplicate numbers.
• Only students who have a spare set of gym clothes can lend gym clothes to another student.
• A student who brought a spare set of gym clothes may also have had their gym clothes stolen. In that case, assume this student only lost one set of gym clothes, and since they only have one set remaining, they cannot lend gym clothes to another student.

Example #1

If student 1 lends gym clothes to student 2, and student 3 or student 5 lends gym clothes to student 4, then all 5 students can attend the gym class.

Example #2

If student 3 lends gym clothes to student 2 or student 4, then 4 students can attend the gym class.

There are three types of students: those who only have their own gym clothes, those who have a spare set, and those whose gym clothes were stolen. Among these, students whose gym clothes were stolen can borrow gym clothes from a student with a spare set, but only from the student right before or right after them. In other words, even if there's a spare available, it can't be lent if the two students aren't adjacent.

lost and reserve record student numbers, and since the order of students matters a great deal in this problem, sorting is essential.

Declare a clothes array to count the number of gym clothes each student has.

JAVA
// Count students who have a spare set of gym clothes
for (int item : reserve)
{
	clothes[item - 1]++;
}

// Count students whose gym clothes were stolen
for (int item : lost)
{
	clothes[item - 1]--;
}

Use a for loop to add or subtract the gym clothes count. A student's number can be treated the same as the array index + 1.

JAVA
import java.util.Arrays;

/**
 * Gym Clothes class
 *
 * @author RWB
 * @since 2021.12.10 Fri 23:38:35
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param n: [int] total number of students
	 * @param lost: [int[]] students whose gym clothes were stolen
	 * @param reserve: [int[]] students who have a spare set of gym clothes
	 *
	 * @return [int] the maximum number of students who can attend gym class
	 */
	public int solution(int n, int[] lost, int[] reserve)
	{
		int[] clothes = new int[n];
		
		// Since gym clothes can only be lent to the adjacent student, the order of student numbers matters
		Arrays.sort(lost);
		Arrays.sort(reserve);
		
		// Count students who have a spare set of gym clothes
		for (int item : reserve)
		{
			clothes[item - 1]++;
		}
		
		// Count students whose gym clothes were stolen
		for (int item : lost)
		{
			clothes[item - 1]--;
		}
		
		for (int i = 0; i < clothes.length; i++)
		{
			// If this student had their gym clothes stolen
			if (clothes[i] == -1)
			{
				// If not the first student, and the previous student has a spare
				if (i != 0 && clothes[i - 1] == 1)
				{
					clothes[i - 1]--;
					clothes[i]++;
				}
				
				// If not the last student, and the next student has a spare
				else if (i != clothes.length - 1 && clothes[i + 1] == 1)
				{
					clothes[i + 1]--;
					clothes[i]++;
				}
			}
		}
		
		return Arrays.stream(clothes).filter(value -> value > -1).toArray().length;
	}
}