【贪心练习】工作安排求调

Question

【问题描述】
有 n 个任务，每个任务有一个截止完成的时间 Ci
和完成需要的时间 Ti 。现在你一个人希望从 0 时刻开始完成尽量多的任务。问最多能完成多少任务？

【输入格式】
第 1 行为一个整数 n ；
以下 n 行描述n 个任务，其中第i+1 行描述第i 个任务，每行有两个整数Ti 和 Ci ；

【输出格式】
输出文件仅一个整数为最多完成的任务个数。

【样例输入1】
3
3 5
2 3
1 1
【样例输出1】
2

我样例过了，但测试点全WA了。
我的想法是将这个时间转换为一个个时间区间线段，求最多个没有重叠的线段数。
附上我的c++代码：

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
ll n;
struct node{
    ll x , y;
    int xb;
}input[100005];

bool cmp(node a , node b){
    return a.y < b.y;
}


void solve()
{
    scanf("%lld" , &n);
    for (int i = 1 ; i <= n ; i++)
    {
        ll x , y;scanf("%lld%lld" , &x , &y);
        input[i].x = max(y - x , 0ll) , input[i].y = y;
        input[i].xb = i;
    }
    sort (input + 1 , input + 1 + n , cmp);
    
    int sum = 1;
    int r = input[1].y;
    
    for (int i = 1 ; i <= n ; i++)
    {
        if (r <= input[i].x)
        {
            r = input[i].y;
            sum++;
//            cout << i <<endl;
        }
//        cout << input[i].xb << endl;
    }
    
    printf("%d" , sum);
}
int main() 
{
    solve();
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

你的代码实现思路基本正确，但在处理某些特定情况时可能会出现问题。这里的问题在于当两个任务结束时间相同且开始时间也相同时，你的代码可能无法正确地计算它们。在排序后，这样的任务会被认为是重叠的，但实际上它们是可以同时执行的。为了解决这个问题，我们可以稍微调整一下比较函数（cmp）以及处理过程。

以下是修改后的代码，对输入进行两次排序，首先按照截止日期升序排列，然后对于截止日期相同的任务按照开始时间降序排列。这样可以确保在截止日期相同时，优先考虑那些开始时间更早的任务，从而避免遗漏这些可以并行执行的任务。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Node {
    int start, end, index;
};

bool compareByEnd(Node& a, Node& b) {
    return a.end < b.end || (a.end == b.end && a.start > b.start);
}

bool compareByIndex(Node& a, Node& b) {
    return a.index < b.index;
}

int main() {
    int n;
    cin >> n;
    vector<Node> tasks(n);

    for (int i = 0; i < n; ++i) {
        int start, end;
        cin >> start >> end;
        tasks[i] = {start, end, i};
    }

    // First sort by end time in ascending order, then by start time in descending order
    sort(tasks.begin(), tasks.end(), compareByEnd);
    sort(tasks.begin(), tasks.end(), compareByIndex);

    int count = 1, lastEndTime = tasks[0].end;
    for (int i = 1; i < n; ++i) {
        if (tasks[i].start >= lastEndTime) {
            count++;
            lastEndTime = tasks[i].end;
        }
    }

    cout << count << endl;
    return 0;
}

这段代码应该可以解决你的问题，并通过所有的测试用例。如果你还有其他疑问或遇到新的问题，请随时告诉我。