Solution
These are th only three cases possible for placing families in each row:
- Place two families when seats 2 to 5 and 6 to 9 are vacant
- Place one family when seats 2 to 5 or 6 to 9 are vacant
- Place one family when seats 4 to 7 are vacant
We can keep three booleans to check whether there is any filled seat amongst 2 to 5, 4 to 7, and 6 to 9.
Approach 1
Have a 2D vector where no. of rows = n and no. of columns = 10 representing all the seats in the cinema. Set arr[i][j] to be false if seat j in row i is not vacant and then check for the three booleans for each row i. We can do better on both time and space complexity. For one, consider that only 10 seats are reserved in a cinema having 100 seats. Storing information about all the seats occupies a lot of space.
Approach 2
Have a hash map which stores all the reserved seats for a row. Then, compute the value of the three booleans defined above for each row in the map. If a row number is not present in the map, it means that it is completely vacant so we can place two families in it. We can still do just a little better by storing directly the three booleans instead.
Approach 3
Have a hash map which stores the three booleans for a row. Then, check for the value of the three booleans defined above for each row in the map. If a row number is not present in the map, it means that it is completely vacant so we can place two families in it.
int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
int res = 0;
unordered_map<int, vector<bool>> reservedMap;
for (auto v : reservedSeats) {
if (reservedMap.find(v[0]) == reservedMap.end())
reservedMap[v[0]] = vector<bool>(3, true);
if (v[1]>=2&&v[1]<=5)
reservedMap[v[0]][0] = false;
if (v[1]>=4&&v[1]<=7)
reservedMap[v[0]][1] = false;
if (v[1]>=6&&v[1]<=9)
reservedMap[v[0]][2] = false;
}
for (auto x : reservedMap) {
if (x.second[0]&&x.second[2])
res+=2;
else if (x.second[0] || x.second[1] || x.second[2])
res+=1;
}
res += 2*(n-reservedMap.size());
return res;
}
Time complexity: O(n)