algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

cinema-seat-allocation.py (1400B)

      1 SEATS_PER_ROW = 10
      2 NUM_PEOPLE = 4
      3 
      4 def compute(n, reservedSeatsDict):
      5     
      6     result = 0
      7 
      8     for y in range(1, n+1):
      9 
     10         running = 0
     11         row = reservedSeatsDict.get(y)
     12 
     13         if row is None:
     14             result += 2
     15             continue
     16 
     17         valid_first = {2,4,6}
     18 
     19         for x in range(1, SEATS_PER_ROW + 1):
     20             if x in valid_first or running > 0:
     21                 if not x in row:
     22                     running += 1
     23                 else:
     24                     running = 0
     25                     continue
     26                 
     27                 if running == NUM_PEOPLE:
     28                     running = 0
     29                     result += 1
     30 
     31     return result
     32 
     33 def reserved_dict(reservedSeats):
     34 
     35     result = {}
     36     current_row = {}
     37     current_row_num = -1
     38 
     39     for seat in reservedSeats:
     40         if seat[0] != current_row_num:
     41             current_row = result.get(seat[0])
     42             current_row_num = seat[0]
     43 
     44         if current_row is None:
     45             result[seat[0]] = {seat[1]}
     46             current_row = result[seat[0]]
     47         else:
     48             # current_row is a set so it is a reference.
     49             current_row.add(seat[1])
     50         
     51     return result
     52 
     53 class Solution:
     54 
     55     def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
     56         reservedSeats.sort()
     57         reservedSeatsDict = reserved_dict(reservedSeats)
     58         return compute(n, reservedSeatsDict)