2286. Booking Concert Tickets in Groups
Description
A concert hall has n
rows numbered from 0
to n - 1
, each with m
seats, numbered from 0
to m - 1
. You need to design a ticketing system that can allocate seats in the following cases:
- If a group of
k
spectators can sit together in a row. - If every member of a group of
k
spectators can get a seat. They may or may not sit together.
Note that the spectators are very picky. Hence:
- They will book seats only if each member of their group can get a seat with row number less than or equal to
maxRow
.maxRow
can vary from group to group. - In case there are multiple rows to choose from, the row with the smallest number is chosen. If there are multiple seats to choose in the same row, the seat with the smallest number is chosen.
Implement the BookMyShow
class:
BookMyShow(int n, int m)
Initializes the object withn
as number of rows andm
as number of seats per row.int[] gather(int k, int maxRow)
Returns an array of length2
denoting the row and seat number (respectively) of the first seat being allocated to thek
members of the group, who must sit together. In other words, it returns the smallest possibler
andc
such that all[c, c + k - 1]
seats are valid and empty in rowr
, andr <= maxRow
. Returns[]
in case it is not possible to allocate seats to the group.boolean scatter(int k, int maxRow)
Returnstrue
if allk
members of the group can be allocated seats in rows0
tomaxRow
, who may or may not sit together. If the seats can be allocated, it allocatesk
seats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returnsfalse
.
Example 1:
Input ["BookMyShow", "gather", "gather", "scatter", "scatter"] [[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]] Output [null, [0, 0], [], true, false] Explanation BookMyShow bms = new BookMyShow(2, 5); // There are 2 rows with 5 seats each bms.gather(4, 0); // return [0, 0] // The group books seats [0, 3] of row 0. bms.gather(2, 0); // return [] // There is only 1 seat left in row 0, // so it is not possible to book 2 consecutive seats. bms.scatter(5, 1); // return True // The group books seat 4 of row 0 and seats [0, 3] of row 1. bms.scatter(5, 1); // return False // There is only one seat left in the hall.
Constraints:
1 <= n <= 5 * 104
1 <= m, k <= 109
0 <= maxRow <= n - 1
- At most
5 * 104
calls in total will be made togather
andscatter
.
Solutions
Solution 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
|