CODEWITHSUNDEEP
recursiondynamic-programmingmemoization
PeraltaLearns
PeraltaLearns

Reputation: 55

Dynamic Programming: Number of Seating Arrangements

This was the bar-raiser question at a company I recently interviewed at. The premise is, a movie theatre has to follow a distance rule where every two seated individuals must have at least six feet distance between them. We are given a list of N non-negative integers where list[k] is the distance between seat k and seat k + 1 and a single row has N+1 seats. We need to figure out the number of valid seating arrangements.

EDIT: After thinking about it more this is what I got so far

def count(seats):
    # No seats then no arrangements can be made
    if seats == 0:
        return 0
    elif seats == 1:
        # 1 seat means 2 arrangements -- leave it empty (skip) or occupy it
        return 2
    
    if list[seats-1] < 6:
       return count(seats - 1) + counts(seats - k(seats))
    else:
       return count(seats - 1)

Recall that list will contain the distance between seat i and seat i+1 so at every seat I will check if the distance between the current seat and the previous one is >= 6 or < 6. If its less than 6 then I can skip the current seat or I can occupy it. Now here's the tricky bit, if I decide to occupy the seat my subproblem is not seats - 1, it will seats - (# of seats to skip to get to the next valid seat). I'm not sure how to find this one. The other case is more trivial, where the distance between the previous seat and current is >= 6 so whether I occupy the current seat or not my subproblem, number of seats, shrinks by one.

Upvotes: 1

Views: 2245

Answers (1)

Eloy P&#233;rez Torres
Eloy P&#233;rez Torres

Reputation: 1177

You can use two pointer technique and dynamic programming to solve this problem.
Here dp[i] stands for the number of valid combinations where ith seat is the last one used (last -> greatest index).

Code:

def count(distances):
    pref_dist = answer = 0
    pos = pos_sum = pos_dist = 0
    dp = [1] * (len(distances) + 1)
    for i in range(len(distances)):
        pref_dist += distances[i]
        while(pref_dist - pos_dist >= 6):
            pos_dist += distances[pos]
            pos_sum += dp[pos]
            pos += 1
        dp[i + 1] += pos_sum
    return sum(dp) + 1

Time complexity:
It is O(n) where n is the number of seats (not O(n^2)) because while condition is true at most n times in whole code execution (pointer pos never decreases, every time the condition is true then pos is increased by one and pos upper limit is n) and every operation inside it use a constant amount of time.

Examples:

  1. Six seats and distance array [5, 2, 4, 1, 2]
    count([5, 2, 4, 1, 2]) -> 16
    These are the valid combinations (1 means taken):
    000000 101000 000010 100001
    100000 000100 100010 010001
    010000 100100 010010 001001
    001000 010100 000001 101001

  2. Four seats and distance array [8, 10, 16]
    count([8, 10, 6]) -> 16
    Every combination is a valid combination. Four seats => 2^4 combinations.

Upvotes: 2

Related Questions