2589. 完成所有任务的最少时间（区间取点——贪心or线段树）

模板题目

• https://www.acwing.com/problem/content/907/
• 题意是给一些区间，问至少取多少个点，让所有区间里至少有一个点
• 上面这个是区间选点的模板贪心
• 按照右端点排序，可以发现相邻的区间只有三种情况
  1. $L_2 \leq L_1 \leq R_1 \leq R_2$
  2. $L_1 \leq L_2 \leq R_1 \leq R_2$
  3. $L_1 \leq R_1 \leq L_2 \leq R_2$
• 所以得出结论，贪心的想，选点在每个区间最后面开始，能满足最优的情况

题目

• https://leetcode.cn/problems/minimum-time-to-complete-all-tasks/description/

思路1————贪心

• 这个就是上面题目的升级版，区间选点不再是一个，而是每个区间需要至少选一定数量的点
• 同理，我们只需要用一个run数组来记录那些时间是被使用过的，然后从后往前补上确实的运行时间即可

代码

class Solution {
public:
    int findMinimumTime(vector<vector<int>>& tasks) {
        sort(tasks.begin(),tasks.end(),[&](vector<int> &a,vector<int> &b)
        {
            return a[1] < b[1];
        });

        int run[2023] = {0};
        int ans = 0;
        for(auto task:tasks)
        {
            int l = task[0],r = task[1],ti = task[2];
            int has_run = 0;
            for(int i = l;i <= r;i ++)
            {
                has_run += run[i];
            }
            if(has_run >= ti)continue;

            for(int i = r;i >= l;i --)if(ti > has_run)
            {
                if(!run[i])
                {
                    has_run ++;
                    run[i] = 1;
                    ans ++;
                }
            }
        }

        return ans;
    }
};

思路2————贪心+线段树

• 贪心思路和上面一样
• 只不过用上了线段树的区间修改
• 优先修改右子树
• 找到从未更新过的子线段，然后判断是否数量足够、是否已满、是否被用过，然后再更新答案
• 带入的更新value可以用引用
• 然后返回，判断value > 0

代码

class Solution {
typedef long long LL;

const static int N = 2100;
// int n, m;
// int w[N];
struct Node
{
    int l, r;
    LL sum, add;//现实点数，子树有的lazy
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        //传递懒标记，更新子树
        left.add = root.add, left.sum = (LL) (left.r - left.l + 1) * root.add;
        right.add = root.add, right.sum = (LL) (right.r - right.l + 1) * root.add;
        //删除父结点懒标记
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int &v)//修改的modify
{
    if(tr[u].sum == tr[u].r - tr[u].l + 1)return ;
    if (l <= tr[u].l && tr[u].r <= r && tr[u].sum == 0 && tr[u].r - tr[u].l + 1 <= v)
    {
        v -= tr[u].r - tr[u].l + 1;
        tr[u].sum = (tr[u].r - tr[u].l + 1);
        tr[u].add = 1;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (r > mid && v > 0) modify(u << 1 | 1, l, r, v);
        if (l <= mid && v > 0) modify(u << 1, l, r, v);
        
        pushup(u);
    }
}
LL query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v += query(u << 1 | 1, l, r);
    return v;
}

public:
    int findMinimumTime(vector<vector<int>>& tasks) {
        sort(tasks.begin(),tasks.end(),[&](vector<int> &a,vector<int> &b)
        {
            return a[1] < b[1];
        });

        build(1,1,tasks.back()[1]);

        for(auto task:tasks)
        {
            int l = task[0],r = task[1],ti = task[2];
            ti -= query(1,l,r);
            if(ti > 0)modify(1,l,r,ti);
            
        }

        return query(1,1,tasks.back()[1]);
    }
};

最后

• 又学到了新的线段树