algo-aha

区间问题大都是贪心法

最多的不重叠区间数

最早结束时间优先，给其他区间腾出空间。用end记录已选区间的最右端，比较当前区间起点和end，不重叠则可选当前区间。

• https://leetcode.com/problems/non-overlapping-intervals/
• https://leetcode.com/problems/maximum-length-of-pair-chain/
• https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

int findMinArrowShots(vector<vector<int>>& points) {
    // 找最多的不重叠区间数
    sort(points.begin(), points.end(), [](const vector<int> &a, const vector<int> &b) {
        return a[1] < b[1];
    });
    int ans = 0;
    long end = LONG_MIN;
    for (auto &p : points) {
        if (p[0] > end) {
            end = p[1];
            ans++;
        }
    }
    return ans;
}

带权重的区间，总权重最大的不重叠区间

要用动态规划+二分搜索

• https://leetcode.com/problems/maximum-profit-in-job-scheduling

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    // 先按endTime排序
    const int N = startTime.size();
    vector<array<int, 3>> jobs;
    for (int i = 0; i < N; i++) {
        jobs.push_back({ endTime[i], startTime[i], profit[i] });
    }
    sort(begin(jobs), end(jobs));

    // 设dp[endTime]表示到某endTime的maxProfit
    map<int, int> dp; // endTime=>maxProfit
    dp[0] = 0; // 左哨兵
    for (auto& [e, s, p] : jobs) {
        // 对每个job找它前面与它相容的最后一个区间
        // 相容，即toFind.endTime<=cur.startTime
        int preMaxP = prev(dp.upper_bound(s))->second;
        int curMaxP = preMaxP + p;
        // 利润比已知更大，选择当前区间
        if (curMaxP > dp.rbegin()->second) dp[e] = curMaxP;
    }
    return dp.rbegin()->second;
}

尽量多地上课程

• https://leetcode.com/problems/course-schedule-iii/

课程(t,d)有持续时间t、最晚结束时间d。列举两个课程(a,x),(b,y)比较的所有情况（a+b<=x、x<a+b<=y、y<a+b；a<=b、a>b；假设x<y）可知：最晚结束时间优先总没错。这结论跟“最多的不重叠区间数”一样，尽管这里是最晚结束时间，那里是实际结束时间。

实际结束时间和最晚结束时间的区别在于，若当前课程跟前面区间重叠，实际结束时间的情况下当前课程不能选，最晚结束时间的情况下：当前课程可以替换掉已选课程中持续时间t最大、且t比当前课程更大的某课程，以腾出更多时间。

int scheduleCourse(vector<vector<int>>& courses) {
    sort(courses.begin(), courses.end(), [](const auto &a, const auto &b) {
        return a[1] < b[1];
    });
    priority_queue<int> taken; // 已选课程的持续时间t

    int end = 0; // 已选课程的实际结束时间
    for (auto &c : courses) {
        if (end + c[0] <= c[1]) { // 选课程c
            taken.push(c[0]);
            end += c[0];
        } else if (!taken.empty()) { // 替换掉持续时间t最大且更大的已选课程
            int t = taken.top();
            if (t > c[0]) {
                taken.pop();
                taken.push(c[0]);
                end += c[0] - t;
            }
        }
    }
    return taken.size();
}

为使集合S与每个区间交集>=2，集合S最少要有几个数

• https://leetcode.com/problems/set-intersection-size-at-least-two

int intersectionSizeTwo(vector<vector<int>>& intervals) {
    // 区间按right排序，right相同时优先考虑范围小的
    sort(intervals.begin(), intervals.end(), [](vector<int> &a, vector<int> &b) {
        if (a[1] == b[1]) return a[0] > b[0];
        return a[1] < b[1];
    });

    int ans = 0;
    // last1,last2是集合S[..last2,last1]的最后两个数
    int last1 = INT_MIN, last2 = INT_MIN;
    for (auto &interval : intervals) {
        if (last1 < interval[0]) {
            // S与当前区间不相交，要在S中加入当前区间的最后两个数
            ans += 2;
            last1 = interval[1];
            last2 = last1 - 1;
        } else if (last2 < interval[0]) {
            // S与当前区间有一个数相交，要在S中加入当前区间的最后一个数
            ans += 1;
            last2 = last1;
            last1 = interval[1];
        }
    }
    return ans;
}