解法：模拟

因为“当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议”，因此有重要性质：会议开始的相对顺序不会改变。我们只需要按顺序模拟每个会议分配给哪个会议室即可。

复杂度 $\mathcal{O}(m\log m + nm)$，其中 $m$ 是会议的数量。具体实现见参考代码，注意会议的结束时间可能超出 int 的范围。

参考代码（c++）

###c++

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        int m = meetings.size();
        // 将会议按开始时间排序
        sort(meetings.begin(), meetings.end());
        // 每个会议室被分配了多少会议
        vector<int> cnt(n);
        // 每个会议室的最早可用时间
        vector<long long> tim(n);
        // 按顺序处理会议
        for (auto &meet : meetings) {
            // best 表示当前不可用，但可用时间最早的会议室编号
            int best = 0;
            for (int i = 0; i < n; i++) {
                if (tim[i] <= meet[0]) {
                    // 当前会议室可用，直接分配
                    cnt[i]++;
                    tim[i] = meet[1];
                    goto OK;
                } else if (tim[i] < tim[best]) best = i; // 当前会议室不可用，更新 best
            }
            // 当前没有会议室可用，等待会议室 best 可用再分配
            cnt[best]++;
            tim[best] += meet[1] - meet[0];
            OK: continue;
        }
        // 统计答案
        int ans = 0;
        for (int i = 0; i < n; i++) if (cnt[i] > cnt[ans]) ans = i;
        return ans;
    }
};

也可以使用线段树将复杂度降至 $\mathcal{O}(m\log m + m\log n)$。

参考代码（c++）

###c++

class Solution {
    vector<long long> mino;

    // 修改 pos 位置的值为 val
    void modify(int id, int l, int r, int pos, long long val) {
        if (l == r) mino[id] = val;
        else {
            int nxt = id << 1, mid = (l + r) >> 1;
            if (pos <= mid) modify(nxt, l, mid, pos, val);
            else modify(nxt | 1, mid + 1, r, pos, val);
            mino[id] = min(mino[nxt], mino[nxt | 1]);
        }
    }

    // 求编号最小的，且值小等于 val 的位置
    int query1(int id, int l, int r, int val) {
        if (l == r) return l;
        else {
            int nxt = id << 1, mid = (l + r) >> 1;
            if (mino[id] > val) return -1;
            else if (mino[nxt] <= val) return query1(nxt, l, mid, val);
            else return query1(nxt | 1, mid + 1, r, val);
        }
    }

    // 求值最小的位置在哪里
    int query2(int id, int l, int r) {
        if (l == r) return l;
        else {
            int nxt = id << 1, mid = (l + r) >> 1;
            return mino[nxt] <= mino[nxt | 1] ? query2(nxt, l, mid) : query2(nxt | 1, mid + 1, r);
        }
    }

public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        mino.resize(n * 4 + 10);
        int m = meetings.size();
        sort(meetings.begin(), meetings.end());

        vector<int> cnt(n);
        for (auto &meet : meetings) {
            // 是否直接有会议室可用
            int x = query1(1, 0, n - 1, meet[0]);
            if (x >= 0) cnt[x]++, modify(1, 0, n - 1, x, meet[1]); // 直接有会议室可用，更新该会议室的可用时间
            else {
                // 没有会议室直接可用，找接下来最早可用的会议室
                x = query2(1, 0, n - 1);
                // 更新该会议室的可用时间
                cnt[x]++;
                modify(1, 0, n - 1, x, mino[1] + meet[1] - meet[0]);
            }
        }

        // 统计答案
        int ans = 0;
        for (int i = 0; i < n; i++) if (cnt[i] > cnt[ans]) ans = i;
        return ans;
    }
};

解法：枚举 & 前缀和

为了方便计算前（后）缀和，我们认为 customers 的下标是从 $1$ 开始的，最后答案减 $1$ 即可。

维护 $f(i)$ 表示第 $1$ 到第 $i$ 个字符有几个 N（初值 $f(0) = 0$），$g(i)$ 表示第 $i$ 到第 $n$ 个字符有几个 Y（初值 $g(n + 1) = 0$），那么第 $h$ 小时关店的代价即为 $f(h - 1) + g(h)$。

从 $1$ 到 $(n + 1)$ 枚举所有 $h$ 并选出代价最小的即可。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###c++

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();

        int f[n + 2], g[n + 2];
        // 计算前缀有几个 N
        f[0] = 0;
        for (int i = 1; i <= n; i++) f[i] = f[i - 1] + (customers[i - 1] == 'N' ? 1 : 0);
        // 计算后缀有几个 Y
        g[n + 1] = 0;
        for (int i = n; i > 0; i--) g[i] = g[i + 1] + (customers[i - 1] == 'Y' ? 1 : 0);

        // 枚举答案
        int ans = 0, best = 1e9;
        for (int i = 1; i <= n + 1; i++) {
            int tmp = f[i - 1] + g[i];
            if (tmp < best) ans = i, best = tmp;
        }
        return ans - 1;
    }
};

解法：贪心 & 排序

每次应该选择当前幸福值最高的孩子。由于每个孩子在没被选中时，幸福值都会下降相同的量，所以幸福值的相对大小关系不会改变。

因此将孩子按幸福值从大到小排序，依次选择孩子即可。复杂度 $\mathcal{O}(n\log n)$。

参考代码（c++）

###c++

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int K) {
        int n = happiness.size();
        // 将孩子按幸福值排序
        sort(happiness.begin(), happiness.end());
        long long ans = 0;
        // 按幸福值从大到小选择孩子
        for (int i = n - 1; i >= n - K; i--) ans += max(0, happiness[i] - (n - 1 - i));
        return ans;
    }
};