aboutsummaryrefslogtreecommitdiff
path: root/cinema_seat_allocation.c
blob: 30d219598e404a76b40f35618a2fbbf1b678d3a2 (plain)
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
// 1386. Cinema Seat Allocation
#include <stdio.h>
#include <stdlib.h>

/*
 * a cinema has 'n' rows of seats, numbered from 1 to 'n' and there
 * are ten seats in each row, labelled from 1 to 10 as shown in
 * the figure above. given the array 'reserved_seats' containing
 * the number of seats already reserved, for example 'reserved_seats[i]
 * = [3,8]' means the seat located in row 3 and labelled with 8
 * is already reserved. return the maximum number of four-person
 * groups you can assign on the cinema seats. a four-person group
 * occupies four adjacent seats in one single row. seats across
 * an aisle are not considered to be adjacent, but there is an
 * exceptional case on which an aisle split a four-person group
 * in that case the aisle split a four-person group in the middle
 * which means to have two people on each side.
 */

int cmp(const void *a, const void *b) {
  int *new_a = *(int **)a, *new_b = *(int **)b;
  if (new_a[0] == new_b[0])
    return new_a[1] - new_b[1];
  return new_a[0] - new_b[0];
}

int maxNumberOfFamilies(int n, int **reserved_seats, int reserved_seats_size,
                        int *reserved_seats_col_size) {
  qsort(reserved_seats, reserved_seats_size, sizeof(int *), cmp);
  int hash[256] = {}, ans = 2 * n;
  hash[0] = 2;
  for (int i = 1; i < 256; i++) {
    int val = i;
    if (!(val & 0x0F))
      hash[i] = 1;
    else if (!(val & 0xF0))
      hash[i] = 1;
    else if (!(val & 0x3C))
      hash[i] = 1;
  }
  int val = 0, col = reserved_seats[0][1];
  if (col != 1 && col != 10)
    val |= 1 << (col - 2);
  for (int i = 1; i < reserved_seats_size; i++) {
    col = reserved_seats[i][1];
    if (reserved_seats[i][0] == reserved_seats[i - 1][0]) {
      if (col != 1 && col != 10)
        val |= 1 << (col - 2);
    } else {
      ans -= 2 - hash[val];
      val = 0;
      if (col != 1 && col != 10)
        val |= 1 << (col - 2);
    }
  }
  ans -= 2 - hash[val];
  return ans;
}

int main() {
  int n1 = 2, rs1[6][2] = {{1, 2}, {1, 3}, {1, 8}, {2, 6}, {3, 1}, {3, 10}},
      rss1 = 6, rscs1[] = {};
  int n2 = 4, rs2[3][2] = {{2, 1}, {1, 8}, {2, 6}}, rss2 = 3, rscs2[] = {};
  printf("%d\n", maxNumberOfFamilies(n1, rs1, rss1, rscs1));
  printf("%d\n", maxNumberOfFamilies(n2, rs2, rss2, rscs2));
}