AlgoLounge

Cinema Seat Allocation

medium

A cinema has n rows, numbered 1 to n. Every row has ten seats, numbered 1 to 10 from left to right, and two aisles cut through each row — one between seats 3 and 4, the other between seats 7 and 8:

seat:  1  2  3 | 4  5  6  7 | 8  9  10

Some seats are already sold: reservedSeats[i] = [row, seat] means that seat is taken.

Groups of four want to sit together: four seats next to each other in the same row. Seats on opposite sides of an aisle (like 3 and 4) normally don't count as next to each other — except when the aisle splits the group exactly in half, two people on each side.

Return the maximum number of four-person groups that can be seated.

Examples

Example 1

Input:  n = 2, reservedSeats = [[1,5],[2,1],[2,10]]
Output: 3

Row 1 has seat 5 sold, so only seats 6–9 can hold a group. Row 2 only lost its two outer seats, so it still fits two groups (seats 2–5 and 6–9).

Example 2

Input:  n = 3, reservedSeats = [[1,4],[2,6],[2,7],[3,3],[3,8]]
Output: 3

Each row fits exactly one group: row 1 in seats 6–9, row 2 in seats 2–5, and row 3 in the middle, seats 4–7.

Example 3

Input:  n = 1, reservedSeats = [[1,4],[1,7]]
Output: 0

Every way to seat four people together uses seat 4 or seat 7.

Example 4

Input:  n = 1, reservedSeats = [[1,2],[1,9]]
Output: 1

Only the middle block, seats 4–7, is still free.

Example 5

Input:  n = 500000000, reservedSeats = [[1,1]]
Output: 1000000000

Seat 1 isn't part of any group's seats, so every row — including row 1 — fits two groups. With this many rows you can't afford to look at each one.

Constraints

  • 1 <= n <= 5 * 10^8
  • 1 <= reservedSeats.length <= min(10 * n, 10^4)
  • reservedSeats[i].length == 2
  • 1 <= reservedSeats[i][0] <= n
  • 1 <= reservedSeats[i][1] <= 10
  • All reservedSeats[i] are distinct.
TypeScript
Loading editor…
List of test cases (35)
Case 1
n = 3
reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Case 2
n = 2
reservedSeats = [[2,1],[1,8],[2,6]]
Case 3
n = 4
reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Case 4
n = 1
reservedSeats = [[1,1]]
Case 5
n = 1
reservedSeats = [[1,10]]
Case 6
n = 1
reservedSeats = [[1,1],[1,10]]
Case 7
n = 1
reservedSeats = [[1,5]]
Case 8
n = 1
reservedSeats = [[1,6]]
Case 9
n = 1
reservedSeats = [[1,2],[1,9]]
Case 10
n = 1
reservedSeats = [[1,4],[1,7]]
Case 11
n = 1
reservedSeats = [[1,3],[1,8]]
Case 12
n = 1
reservedSeats = [[1,5],[1,6]]
Case 13
n = 1
reservedSeats = [[1,4]]
Case 14
n = 1
reservedSeats = [[1,7]]
Case 15
n = 1
reservedSeats = [[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9]]
Case 16
n = 1
reservedSeats = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,10]]
Case 17
n = 5
reservedSeats = [[3,5]]
Case 18
n = 10
reservedSeats = [[1,1],[1,10],[2,1],[2,10],[3,1],[3,10],[4,1],[4,10],[5,1],[5,10],[6,1],[6,10],[7,1],[7,10],[8,1],[8,10],[9,1],[9,10],[10,1],[10,10]]
Case 19
n = 500000000
reservedSeats = [[1,1]]
Case 20
n = 500000000
reservedSeats = [[250000000,5],[250000000,6]]
Case 21
n = 500000000
reservedSeats = [[500000000,2],[1,9],[1,3]]
Case 22
n = 4
reservedSeats = [[2,4],[4,10],[3,1],[2,5],[1,2],[4,2],[3,4],[2,6]]
Case 23
n = 1
reservedSeats = [[1,10]]
Case 24
n = 3
reservedSeats = [[3,6],[1,1],[3,8],[2,8],[3,2],[2,7],[1,4],[2,4],[2,9],[3,4],[2,1],[3,9],[1,6]]
Case 25
n = 3
reservedSeats = [[2,7]]
Case 26
n = 6
reservedSeats = [[3,6],[2,1],[2,7]]
Case 27
n = 1
reservedSeats = [[1,9],[1,2],[1,4],[1,3],[1,5],[1,8],[1,10],[1,7],[1,6],[1,1]]
Case 28
n = 4
reservedSeats = [[4,9],[3,5],[4,6],[4,5],[1,2]]
Case 29
n = 6
reservedSeats = [[6,2],[1,4],[2,10],[1,10],[1,2],[4,5],[1,8],[6,6]]
Case 30
n = 1
reservedSeats = [[1,6],[1,5],[1,9],[1,10],[1,2],[1,3],[1,1],[1,8],[1,7]]
Case 31
n = 6
reservedSeats = [[6,9],[3,7],[4,7],[4,1],[2,1]]
Case 32
n = 1000
reservedSeats = [[853,7],[785,1],[863,2],[675,9],[863,10],[281,2],[342,6],[186,5],[338,4],[949,7],[370,8],[132,5],[987,3],[939,3],[998,8],[411,10],[346,7],[808,9],[946,2],[991,6],[631,8],[863,5],[466,9],[22,5],[115,1],[304,4],[310,7],[304,6],[498,10],[152,1],[426,9],[273,3],[469,9],[385,7],[107,2],[619,6],[314,1],[103,5],[385,2],[314,10],[697,7],[939,4],[342,10],[430,2],[785,8],[278,8],[419,9],[891,4],[278,4],[738,3],[565,5],[525,3],[426,2],[346,5],[511,2],[587,10],[839,1],[190,8],[907,8],[498,4],[963,1],[304,9],[343,10],[516,5],[939,8],[795,9],[266,2],[157,7],[632,4],[824,7],[393,6],[201,5],[891,5],[405,1],[738,7],[920,1],[900,7],[113,6],[430,8],[991,5],[565,6],[405,7],[212,3],[310,3],[844,5],[736,7],[426,8],[874,10],[949,5],[63,4],[469,8],[619,4],[991,10],[939,6],[785,10],[250,8],[393,10],[824,1],[469,3],[900,2],[576,5],[411,7],[814,7],[692,5],[48,8],[338,1],[69,4],[466,2],[250,4],[63,10],[201,7],[736,9],[103,9],[853,6],[793,10],[278,6],[385,5],[11,3],[314,4],[190,9],[393,8],[144,9],[309,2],[202,5],[569,2],[947,5],[839,9],[557,6],[370,3],[511,1],[793,9],[907,10],[939,7],[234,4],[2,9],[174,8],[645,9],[418,8],[132,4],[314,3],[157,8],[233,6],[565,2],[450,7],[675,3],[325,10],[786,5],[22,1],[498,7],[107,9],[565,4],[576,2],[557,3],[457,7],[418,9],[920,7],[848,4],[946,9],[565,7],[297,10],[113,1],[325,4],[128,5],[946,3],[419,8],[128,10],[785,7],[11,1],[960,8],[157,6],[487,5],[949,3],[925,10],[963,10],[450,2],[202,2],[103,2],[370,1],[118,4],[291,6],[314,7],[863,6],[140,1],[2,5],[511,8],[956,6],[405,4],[457,10],[11,9],[304,2],[469,10],[362,8],[369,5],[516,6],[144,7],[738,10],[22,8],[987,2],[487,9],[450,10],[144,5],[48,1],[393,5],[963,5],[174,2],[839,4],[739,2],[325,8],[281,1],[233,7],[511,3],[839,2],[118,10],[884,6],[310,6],[457,1],[234,9],[569,1],[487,6],[498,2],[343,4],[590,8],[282,3],[874,8],[205,9],[233,2],[675,1],[576,3],[282,8],[450,4],[786,9],[839,8],[281,10],[118,7],[795,4],[103,10],[814,5],[212,4],[174,5],[266,1],[487,4],[419,1],[343,8],[310,9],[920,9],[525,7],[385,6],[281,6],[22,3],[419,6],[310,2],[201,2],[525,10],[342,4],[115,7],[874,2],[370,2],[174,6],[987,9],[291,7],[346,1],[982,10],[282,4],[282,6],[697,10],[516,2],[645,4],[273,7],[426,1],[22,4],[692,1],[569,10],[2,8],[894,2],[888,9],[987,7],[736,8],[525,5],[343,6],[50,6],[785,6],[697,4],[132,2],[631,7],[694,9],[338,6],[814,2],[587,4],[338,7],[157,1],[764,1],[128,7],[888,3],[628,1],[63,6],[808,8],[785,4],[370,6],[152,5],[338,5]]
Case 33
n = 40
reservedSeats = [[34,5],[22,6],[34,3],[3,3],[11,4],[22,3],[16,4],[19,8],[26,6],[34,6],[34,1],[38,9],[34,4],[25,2],[8,2],[23,7],[9,1],[15,10],[24,1],[24,9],[4,5],[32,7],[24,4],[33,4],[18,10],[6,1],[23,4],[16,3],[17,6],[10,4],[19,5],[31,2],[32,4],[11,7],[18,4],[13,8],[1,4],[33,2],[19,9],[11,2],[10,1],[1,7],[31,5],[30,3],[1,5],[33,7],[1,3],[13,10],[17,1],[1,8],[32,10],[22,2],[20,10],[8,1],[7,5],[27,2],[35,1],[25,10],[13,2],[39,4],[37,5],[2,3],[38,4],[18,1],[12,5],[12,1],[38,8],[8,5],[22,7],[2,9],[12,2],[24,3],[33,8],[14,5],[29,8],[31,9],[30,8],[1,10],[14,9],[26,1],[9,7],[38,10],[32,6],[3,1],[17,2],[23,10],[3,8],[23,9],[16,1],[36,7],[38,1],[22,4],[4,10],[2,1],[2,4],[36,6],[30,1],[15,4],[13,6],[21,5],[13,9],[35,5],[3,5],[12,6],[25,4],[26,8],[10,5],[15,1],[5,4],[38,6],[6,3],[14,10],[8,8],[19,4],[11,1],[2,2],[35,10],[19,10],[18,5],[16,2],[28,2],[3,2],[19,2],[31,4],[27,7],[5,10],[19,3],[28,8],[7,4],[36,5],[29,1],[3,4],[4,1],[39,2],[13,5],[10,7],[34,10],[4,6],[14,6],[27,8],[9,9],[24,5],[23,1],[7,8],[28,1],[13,7],[15,2],[29,7],[20,8],[29,4],[38,2],[23,5],[21,1],[30,9],[10,3],[8,6],[30,7],[5,6],[40,9],[2,10],[6,10],[38,7],[9,4],[3,9],[23,2],[22,1],[24,10],[37,2],[14,4],[16,6],[35,4],[2,6],[35,6],[36,9],[7,1],[19,7],[40,10],[12,7],[12,10],[9,8],[25,8],[8,7],[24,2],[34,2],[25,6],[18,7],[16,5],[39,6],[19,1],[15,9],[9,6],[28,6],[6,4],[4,2],[17,4],[15,5],[6,9],[18,9],[37,10],[8,3],[8,4],[2,5],[15,3],[1,1],[7,6],[36,1],[27,10],[37,3],[10,10],[40,4],[33,5],[21,10],[11,10],[37,1],[13,1],[4,8],[31,6],[15,8],[12,4],[6,2],[26,10],[17,5],[21,6],[7,3],[11,3],[39,1],[37,8],[40,7],[5,3],[21,9],[25,7],[14,2],[12,9],[25,3],[31,8],[34,7],[40,6],[33,6],[39,5],[2,7],[29,9],[14,8],[10,6],[19,6],[8,9],[34,8],[35,7],[25,9],[40,1],[28,10]]
Case 34
n = 500000000
reservedSeats = [[482517814,9],[331607028,4],[336444304,1],[145148177,2],[374681245,3],[164942377,2],[324606225,2],[39002936,6],[68797306,7],[357286123,9],[268606641,5],[389961399,3],[404941783,2],[336444304,5],[292392408,5],[292392408,8],[13833535,5],[278223793,3],[242558854,10],[164942377,10],[433708281,5],[278360922,8],[454767788,6],[159631681,3],[324606225,4],[404941783,6],[268606641,6],[158655747,4],[170031573,6],[389961399,1],[442389454,4],[159631681,1],[278223793,4],[420623385,10],[17042091,9],[326709357,9],[158655747,10],[61828281,6],[206836951,7],[13833535,4],[170031573,10],[161202736,2],[420623385,4],[164942377,5],[234926892,7],[436512891,8],[401016562,7],[336444304,6],[278360922,4],[291572897,6],[371496245,2],[200960389,3],[442423004,3],[466904568,3],[436512891,10],[150772732,6],[357286123,3],[152423271,5],[213220469,2],[148317021,6],[268606641,7],[158655747,9],[324606225,3],[89004806,2],[204951735,6],[89185615,7],[357286123,4],[68797306,1],[434708618,5],[482517814,1],[357286123,5],[145148177,1],[449256624,10],[206836951,10],[294941692,10],[204951735,4],[89185615,3],[291572897,9],[61828281,9],[330815133,8],[148317021,3],[331607028,1],[200960389,9],[420623385,2],[324606225,7],[324606225,10],[231511465,7],[206836951,3],[309946515,7],[326709357,2],[204951735,3],[283238373,9],[145148177,8],[17042091,3],[433318607,6],[234926892,10],[89185615,8],[200960389,1],[39002936,2],[268606641,3],[283238373,1],[324606225,9],[466904568,8],[488077266,6],[17042091,2],[39002936,8],[449256624,7],[337360796,4],[278223793,10],[401016562,9],[380511830,6],[389961399,8],[309946515,3],[436512891,5],[13833535,2],[278223793,6],[278360922,6],[170031573,1],[326709357,5],[401016562,4],[442389454,10],[460008850,9],[337360796,3],[294941692,7],[213220469,4],[213220469,5],[164942377,4],[283238373,5],[234926892,8],[17042091,5],[449256624,8],[164942377,1],[326709357,3],[434708618,1],[292392408,4],[279917570,7],[159631681,10],[488077266,1],[331607028,3],[294941692,9],[292392408,3],[206836951,5],[150772732,2],[291572897,4],[86162589,9],[436512891,6],[330815133,4],[278360922,10],[213220469,8],[420623385,8],[309946515,8],[433318607,7],[337360796,1],[161202736,8],[442423004,6],[145148177,6],[13833535,8],[371496245,10],[331607028,2],[231511465,9],[89004806,8],[466904568,2],[89004806,10],[278223793,2],[204951735,5],[231511465,8],[326709357,7],[291572897,10],[89185615,1],[86162589,7],[380511830,3],[206836951,4],[204951735,2],[434708618,4],[460008850,6],[283238373,2],[482517814,7],[442389454,7],[401016562,6],[89004806,3],[73013655,5],[330815133,1],[89004806,6],[324606225,8],[89004806,1],[442423004,9],[161202736,4],[73013655,10],[330815133,3],[389961399,6],[442389454,6],[294941692,6],[150772732,7],[164942377,9],[164942377,7],[436512891,7],[279917570,5],[68797306,10],[357286123,10],[161202736,5]]
Case 35
n = 123456789
reservedSeats = [[97114306,5],[54980574,8],[26142619,5],[64197322,6],[117373987,8],[24951908,8],[86603543,5],[80855217,1],[29159793,6],[110150289,6],[27413361,3],[86603543,8],[86645855,2],[113090295,3],[43103106,4],[104032581,2],[58071548,6],[58071548,10],[24951908,7],[103008842,8],[863156,8],[3640857,5],[83794368,6],[17152338,6],[59082320,5],[45627955,4],[108128500,4],[4277392,6],[113090295,6],[36881067,4],[81821438,7],[53622804,7],[54980574,6],[54225267,3],[2950771,9],[19506771,4],[54168783,2],[42085233,8],[48902133,3],[62615626,5],[47549985,7],[107279501,2],[863156,9],[73395756,2],[110150289,8],[37171636,1],[96835420,9],[54168783,3],[99604998,5],[118109503,9],[119071850,5],[91253826,7],[110601585,2],[110601585,5],[93066177,9],[112523024,10],[93066177,3],[42085233,3],[107634269,7],[72435125,10],[99604998,4],[23260143,5],[72929652,4],[94343832,4],[119951827,2],[68681385,9],[53892070,3],[17152338,1],[98768494,3],[53892070,4],[114227957,7],[76817115,5],[7638019,8],[117373987,9],[99604998,9],[57013747,8],[9973131,9],[87071211,8],[249430,9],[103008842,7],[112050629,8],[29159793,2],[72039175,4],[42832505,9],[4277392,9],[81422517,2],[68681385,5],[22627247,7],[57381886,6],[25886454,10],[96701045,8],[88034817,1],[5562412,4],[104595264,3],[67539076,9],[28018874,10],[63005113,6],[110343058,9],[59082320,4],[76817115,9],[76817115,3],[11915151,2],[77247796,6],[4277392,8],[19219390,2],[107279501,1],[21030756,4],[42303711,3],[63005113,3],[96835420,1],[24951908,3],[24951908,2],[77247796,3],[36881067,9],[25749409,7],[99053176,10],[97114306,4],[79341796,7],[52566414,5],[80855217,4],[104595264,1],[47549985,8],[99053176,5],[72929652,6],[97142448,9],[7638019,10],[85709289,3],[29159793,1],[29159793,9],[64754912,1],[26142619,10],[19902229,3],[119071850,8],[43135141,1],[53622804,4],[21429080,5],[17152338,9],[119118053,6],[81821438,5],[115309321,9],[57627234,10],[22332351,7],[81422517,10],[109885557,3],[117906758,8],[3640857,4],[68597067,10],[108767934,1],[70291773,2],[5562412,2],[43103106,9],[97114306,10],[107279501,6],[28018874,8],[98768494,2],[86645855,7],[34215609,7],[25886454,2],[14034049,10],[37171636,10],[18622132,7],[47549985,5],[64433634,9],[94343832,5],[14034049,1],[112523024,9],[21429080,9],[42085233,9],[12530099,8],[7638019,1],[53892070,10],[112523024,8],[13596025,8],[42832505,2],[50481292,10],[28506007,4],[108128500,5],[63005113,8],[67539076,3],[117906758,7],[7638019,3],[863156,2],[107279501,10],[19219390,8],[64754912,10],[42303711,7],[104032581,6],[13596025,9],[27413361,10],[68681385,2],[88034817,2],[79341796,8],[57381886,7],[104032581,10],[34215609,9],[28506007,1],[36996154,9],[108767934,5],[37171636,9],[96835420,8],[94343832,9],[113174005,9],[57433169,5],[108128500,8],[53117572,9],[87071211,2],[18622132,5],[115309321,4],[57627234,6],[21030756,9],[19240509,2],[28018874,3],[12138154,1],[82906484,3],[27413361,8],[12530099,6],[43135141,6],[94343832,1],[60875018,9],[78506830,9],[60875018,10],[68597067,4],[20255562,7],[21030756,1],[119262356,5],[119071850,6],[54225267,9],[96701045,2],[58956936,5],[16752192,5],[19902229,8],[58071548,8],[117373987,10],[21429080,6],[5562412,1],[4572924,2],[97114306,1],[104595264,6],[81422517,3],[11915151,1],[72435125,3],[91253826,8],[110150289,10],[12530099,2],[83794368,2],[21429080,1],[98899646,5],[80855217,9],[12530099,3],[97114306,3],[34215609,2],[112050629,9],[52566414,10],[82906484,8],[115309321,5],[83794368,8],[58071548,2],[98768494,1],[97786712,5],[76817115,10],[29582903,6],[5562412,10],[42832505,1],[108128500,1],[97142448,1],[19219390,1],[25886454,5],[57627234,3],[94343832,6],[82524363,6],[19902229,4],[108767934,10],[4572924,1],[9227178,9],[57433169,3],[110150289,9],[8355296,9],[14034049,7],[58071548,1],[67539076,6],[50481292,9],[72039175,5],[57013747,4],[82906484,2],[26142619,8],[110343058,7],[42832505,3],[23260143,4],[53117572,10],[108767934,3],[52170821,4],[12138154,5],[109885557,8],[97786712,1],[28506007,6],[99604998,8],[81821438,2],[62615626,4],[119118053,1],[18622132,8],[72929652,7],[24951908,6],[20255562,9],[64433634,7],[2950771,3],[25749409,9],[16752192,8],[12530099,7],[52170821,9],[2950771,4],[28506007,2],[64754912,2],[86603543,2],[64197322,8],[47549985,10],[97754500,2],[19240509,5],[53622804,8],[97142448,6],[106235892,3],[54168783,6],[25886454,6],[21429080,2],[24196965,5],[62615626,9],[77247796,5],[57013747,7],[81422517,6],[89977603,5],[63005113,4],[110343058,5],[64197322,4],[58956936,4],[53622804,3],[72039175,2],[76905878,6],[119071850,1],[16752192,1],[54168783,8],[36881067,3],[63005113,9],[76905878,3],[17152338,8],[42085233,7],[113174005,8],[76817115,7],[107634269,3],[9227178,6],[54168783,9],[25886454,8],[109885557,2],[36881067,10],[52566414,3],[25749409,10],[107279501,8],[81422517,5],[43769481,4],[82524363,3],[86645855,6],[99053176,3],[36881067,2],[110601585,1],[5562412,7],[34215609,1],[9973131,1],[86645855,3],[19506771,7],[42171490,9],[8765384,8],[104595264,5],[89977603,10],[55431830,5],[83794368,1],[118109503,3],[72435125,6],[19240509,9],[53892070,9],[3640857,1],[57013747,3],[24951908,5],[119118053,4],[24196965,1],[55431830,1],[82906484,4],[57433169,10],[98899646,4],[863156,1],[21030756,10],[45627955,2],[100535477,7],[4277392,3],[44902918,8],[29159793,7],[60875018,3],[60875018,8],[112050629,7],[36996154,7],[68597067,3],[19240509,8],[36881067,7]]