leetcode-1386

题目：

1386. 安排电影院座位

关键词：位运算，二维指针排序

思路：

先排序，再按每一行计算（要么连续8个空位，要么连续4个空位）；可能用例：总行数 > 给出的占位的行数，剩余的行都应该满足连续8个空位。因此：
if (j == reservedSeatsSize) {
count += (n - rowIdx) * 2;
break;
}

1386.c

//
//
// 如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。
//
// 给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[i]=[3,8] ，它表示第 3 行第 8 个座
//位被预约了。
//
// 请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座
//位，但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。
//
//
//
// 示例 1：
//
//
//
// 输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
//输出：4
//解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，橙色的连续座位表示一个 4 人家庭。
//
//
// 示例 2：
//
// 输入：n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
//输出：2
//
//
// 示例 3：
//
// 输入：n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
//输出：4
//
//
//
//
// 提示：
//
//
// 1 <= n <= 10^9
// 1 <= reservedSeats.length <= min(10*n, 10^4)
// reservedSeats[i].length == 2
// 1 <= reservedSeats[i][0] <= n
// 1 <= reservedSeats[i][1] <= 10
// 所有 reservedSeats[i] 都是互不相同的。
//
// Related Topics 贪心算法 数组


//leetcode submit region begin(Prohibit modification and deletion)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

#define MY_DEBUG printf
//#define MY_DEBUG
#define MLOGD(x, fmt...)        MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
//#define MLOGD(x, fmt...)
#define MLOGI(x, fmt...)        MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
#define MLOGE(x, fmt...)        MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
#define ARRAY_SIZE(x)           (sizeof(x) / sizeof(x[0]))

#define COL_SIZE_MAX            10

typedef struct {
    bool seat[COL_SIZE_MAX];
} RowSeatsInfoType;

static int CmpMinor(const void *arg0, const void *arg1)
{
    int **ptr0 = (int **)arg0;
    int **ptr1 = (int **)arg1;
    int row0 = ptr0[0][0];
//    int col0 = ptr0[0][1];
    int row1 = ptr1[0][0];
//    int col1 = ptr1[0][1];
//    MLOGI("row0=%d, col0=%d, row1=%d, col1=%d\n", row0, col0, row1, col1);
    return row0 - row1;
}

int maxNumberOfFamilies(int n, int** reservedSeats, int reservedSeatsSize, int* reservedSeatsColSize)
{
    if ((n <= 0) || (reservedSeatsSize < 0)) {
        MLOGE("invaid arg\n");
        return 0;
    }
    if ((reservedSeats == NULL) || (reservedSeatsColSize == NULL)) {
        MLOGE("invalid ptr\n");
        return 0;
    }
    uint16_t seats;
    qsort(reservedSeats, reservedSeatsSize, sizeof(int *), CmpMinor);
    int i, j;
    int count = 0;
    int rowIdx = 0;
    unsigned int row;
    MLOGI("n=%d, reservedSeatsSize=%d\n", n, reservedSeatsSize);
    for (i = 0, j = 0; i < n; i++) {
        if (j == reservedSeatsSize) {
            count += (n - rowIdx) * 2;
            break;
        }
        seats = 0;
        do {
            row = reservedSeats[j][0];
            MLOGI("j=%d, row=%d, col=%d\n", j, row, reservedSeats[j][1]);
            seats |= (1u << (uint32_t)(reservedSeats[j][1] - 1));
            j++;
        } while ((j < reservedSeatsSize) && (row == reservedSeats[j][0]));
        rowIdx++;
        if ((seats & 0x1FEu) == 0) {
            MLOGD("2 available\n");
            count += 2;
        } else if (((seats & 0x1Eu) == 0) || ((seats & 0x78u) == 0) || ((seats & 0x1E0u) == 0)){
            MLOGD("1 available\n");
            count += 1;
        }
    }
    MLOGI("count = %d\n", count);
    return count;
}

test_case.c

TEST(FactorialTest, test_case1) {
    int n = 3;
    int row1[] = {1, 2};
    int row5[] = {1, 3};
    int row3[] = {1, 8};
    int row4[] = {2, 6};
    int row2[] = {3, 1};
    int row6[] = {3,10};
    int *reservedSeats[] = {row1, row2, row3, row4, row5, row6};
    int reservedSeatsColSize[] = {2, 2, 2, 2, 2, 2};
    int ret = maxNumberOfFamilies(n, reservedSeats, 6, reservedSeatsColSize);
    const int expect = 4;
    std::cout << "ret:"  << ret << std::endl;
    GTEST_ASSERT_EQ(expect, ret);
}

TEST(FactorialTest, test_case2) {
    int n = 4;
    int row1[] = {4,3};
    int row2[] = {1,4};
    int row3[] = {4,6};
    int row4[] = {1,7};
    int *reservedSeats[] = {row1, row2, row3, row4};
    int reservedSeatsColSize[] = {2, 2, 2, 2, 2, 2};
    int ret = maxNumberOfFamilies(n, reservedSeats, 4, reservedSeatsColSize);
    const int expect = 4;
    std::cout << "ret:"  << ret << std::endl;
    GTEST_ASSERT_EQ(expect, ret);
}

TEST(FactorialTest, test_case3) {
    int n = 3;
    int row1[] = {2,3};
    int *reservedSeats[] = {row1};
    int reservedSeatsColSize[] = {2};
    int ret = maxNumberOfFamilies(n, reservedSeats, 1, reservedSeatsColSize);
    const int expect = 5;
    std::cout << "ret:"  << ret << std::endl;
    GTEST_ASSERT_EQ(expect, ret);
}