We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Students Taking Exam

Difficulty: Hard

Problem Description

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character. Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible. Students must be placed in seats in good condition.

Key Insights

  • Students can only see answers from adjacent seats (left, right, upper left, upper right).
  • The placement of students can be optimized using bitmasking to represent seat availability.
  • The problem can be solved using a backtracking approach to explore all possible seating arrangements.

Space and Time Complexity

Time Complexity: O(2^(m * n)) - In the worst case, we check all possible combinations of seating arrangements. Space Complexity: O(m) - For storing current placements and results.

Solution

To solve this problem, we utilize a backtracking algorithm with bitmasking. Each row of the seating arrangement can be represented as a bitmask of available seats. The algorithm iterates through each row, trying to place students while ensuring that no two students can cheat by checking the visibility constraints (adjacent seats). We keep track of the maximum number of students placed without violating the visibility rules.

Code Solutions

def maxStudents(seats):
    m, n = len(seats), len(seats[0])
    # Create a list to hold the bitmask for each row
    row_masks = []
    
    for row in seats:
        mask = 0
        for j in range(n):
            if row[j] == '.':
                mask |= (1 << j)
        row_masks.append(mask)

    def canPlace(row, prev_mask, curr_mask):
        # Check if current mask is valid with respect to prev_mask
        if curr_mask & (curr_mask << 1):  # No two students in adjacent seats
            return False
        if (curr_mask & prev_mask) != 0:  # No student in curr_mask should be in the same column as prev_mask
            return False
        return True

    def backtrack(row, prev_mask):
        if row == m:
            return 0  # Base case, no more rows to process
        max_students = backtrack(row + 1, 0)  # Skip current row
        for curr_mask in range(row_masks[row] + 1):
            if (curr_mask & row_masks[row]) == curr_mask and canPlace(row, prev_mask, curr_mask):
                # Count number of bits set in curr_mask (students placed)
                students_count = bin(curr_mask).count('1')
                max_students = max(max_students, students_count + backtrack(row + 1, curr_mask))
        return max_students

    return backtrack(0, 0)
← Back to All Questions