T1

链接：2409. 统计共同度过的日子数
难度：Easy

分析

题目可以拆解成两个小问题

1. 求两个区间的公共区间。左端点取max，右端点取min，中间部分即为公共区间（可能不存在）
2. 两个日期比大小、求天数差。首先暴力去写比较规则当然是可以的，不过方便起见，可以把日期转换为从1月1日到指定日期的天数再比大小/求差

时间复杂度

转换四个日期，求差，常数复杂度$O(1)$

实现

class Solution {
public:
    int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        int aa = get(arriveAlice), la = get(leaveAlice);
        int ab = get(arriveBob), lb = get(leaveBob);

        return max(0, min(la, lb) - max(aa, ab) + 1);
    }

    int get(string &s) {
        int m = (s[0] - '0') * 10 + s[1] - '0';
        int d = (s[3] - '0') * 10 + s[4] - '0';
        int res = d;
        for (int i = 1; i < m; i++) {
            res += day[i];
        }
        return res;
    }
};

T2

链接：2410. 运动员和训练师的最大匹配数
难度：Medium

分析

二分图的最大匹配

看到题第一反应就是二分图的最大匹配。运动员为一组点，训练师为另一组点，对于一对运动员i和训练师j，如果players[i] <= trainers[j]，视为i和j之前存在一条边。这样就构造了一个二分图，所求结果就是这个二分图上的最大匹配
求二分图最大匹配可以用匈牙利算法，最坏情况下时间复杂度为$O(V \times E)$，其中V为匹配起点的点集个数（可以是players和trainers中任一数组的长度），E为二分图中的边数。本题中最坏情况下（trainers中的任意值都大于players中的每一个值），E为两个数组大小的乘积。所以最坏时间复杂度为$O(n^3)$
考虑到题目的数据范围，基本可以确定这个解法会超时

贪心

从小到大遍历每一个运动员i，寻找第一个大于等于i的训练师j，把j匹配给i，可以成功匹配的对数就是所求的最大匹配
正确性证明：使用构造法证明。假设对于一个最优解，其中存在运动员x，x的匹配为y，而第一个大于等于x的训练师为z，此时

• 如果z没有被别的运动员匹配，取消x和y的匹配，构造x和z的匹配。最大匹配数没有发生变化
• 如果z被运动员w匹配，那么由已知x <= z <= y, w <= z，可以得到w <= y。把x和w的匹配对象交换，最大匹配数没有发生变化

从小到大遍历最优解中每一个这样的x，通过上述方法构造，总能把一个最优解转换为贪心解，且最大匹配数不变。由此证明，贪心解一定是一种最优解

时间复杂度

对两个数组进行排序（两个数组长度数量级相当），遍历两个数组求最大匹配，总体来看$O(nlogn)$

实现

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        sort(players.begin(), players.end());
        sort(trainers.begin(), trainers.end());

        int res = 0;
        for (int i = 0, j = 0; i < players.size() && j < trainers.size(); i++) {
            while (j < trainers.size() && players[i] > trainers[j]) j++;
            if (j < trainers.size() && players[i] <= trainers[j]) {
                res++;
                j++;
            }
        }
        return res;
    }
};

T3

链接：2411. 按位或最大的最小子数组长度
难度：Medium

分析

一个二进制数正数，其中的1越多，则其值越大，让每一个可能为1的位的值都为1就是可能的最大值。而对于或操作，只要操作数中有一个在第i为上出现了1，则结果第i位就为1。所有要求以i开始的按位或运算结果最大的最短子数组，其实就是在求i的右边（包括i）每一位1的最左位置，这些最左位置的最大值就是最短子数组的右边界j（包括j），那么最短子数组的长度就为j - i + 1
数组中元素不超过1e9，转换为2进制数30位即可表示
从右到左遍历数组，对于每一个下标i，求出30个二进制位中每一个二进制位上i右边最左的1的位置j（同时更新每一位1的最左下标），answer[i] = max_j - i + 1

时间复杂度

遍历一次数组，每次遍历枚举30个二进制位，总体看$O(n)$

实现

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> p(30, n);
        vector<int> res(n);

        for (int i = n - 1; i >= 0; i--) {
            int t = i;
            for (int j = 0; j < 30; j++) {
                // 如果nums[i]的第j位是1，更新第j位1的最左坐标
                if ((nums[i] >> j) & 1) p[j] = i;
                // 如果nums[i]的第j位不是1，但是第j位存在1（小于n，最大的1下标是n-1）
                // 那么i的最小子数组至少要到p[j]，多个p[j]取max
                else if (p[j] < n) t = max(t, p[j]);
            }
            res[i] = t - i + 1;
        }
        return res;
    }
};

T4

链接：2412. 完成所有交易的初始最少钱数
难度：Hard

分析

任意交易顺序的最小值，其实就是所有交易顺序最小花费的最大值，即最坏情况下所需的最小money
对于每一笔交易tx，都需要先支付成本c，再拿回收益l，如果c > l，这笔tx就是一个亏钱交易，会抬高对最小money的要求。不难发现，对于任意一笔交易tx，如果要计算在这笔交易开始时所需最小money的最坏情况，一定要把除了这笔交易之外的所有亏钱交易都先进行一遍。遍历所有交易，对于所有交易计算最坏情况，所有最坏情况的max就是全局的最坏情况。
遍历一遍所有交易，计算所有亏钱交易的净亏损之和s。枚举每一笔交易tx

• 如果tx是赚钱交易，此时最少需要的money = s + tx.c
• 如果tx是亏钱交易，此时最少需要的money = s - (tx.c - tx.l) + tx.c = s + tx.l;

正确性证明：假设最优解为A，贪心解为B，证明A = B

• A <= B。对于每一个交易tx，B都满足了tx的最坏情况，显然对于任意一种交易顺序，B都可以保证完成所有交易，即B是问题的一个解。而A是问题的最优解，即A是所有可行解中最小的一个解，所以A <= B
• A >= B。B是枚举每一笔交易最坏情况求得的最大值，假设取得最大值时的交易为tx，那么就可以构造一个顺序：除了tx之外的所有亏钱交易以任意顺序放在tx前面，其他交易放在tx后面。对于这样构造的一个交易顺序，B就是完成所有交易的最小花费。而最优解A要满足任意一种交易顺序，自然也要满足我们构造的这个交易顺序，所以A >= B

时间复杂度

两次遍历，$O(n)$

实现

class Solution {
public:
    long long minimumMoney(vector<vector<int>>& transactions) {
        long long s = 0ll;
        for (auto& tx : transactions) {
            int c = tx[0], l = tx[1];
            if (c > l) s += c - l;
        }

        long long res = 0ll;
        for (auto& tx : transactions) {
            int c = tx[0], l = tx[1];
            long long t = s;
            if (c > l) t -= c - l;
            res = max(res, t + c);
        }
        return res;
    }
};