O(nlogn)复杂度作业调度问题求助：当前仅实现O(n²)解法

我正在解决一个仅涉及截止时间和未执行成本的作业调度问题，教授要求实现O(nlogn)复杂度的解法，但目前我仅能写出O(n²)复杂度的代码。我已尝试用归并排序确定作业顺序，但未找到正确思路。

我的代码 #

int main()
{
    int n;
    scanf("%d", &n);
    int p[n]; //Represents the deadline of the tasks
    int m[n]; //Represents the cost of the tasks

    for (int i = 0; i < n; i++)
        scanf("%d", &p[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &m[i]);

    merge_sort(p, m, 0, n-1); //Sort the array by the cost of task

    int slots[n+1];
    for (int i = 1; i <= n; i++) {
        slots[i] = -1;
    }

    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = p[i]; j >= 0; j--) {
            if (slots[j] == -1) {
                slots[j] = 1;
                break;
            }
            else if (j == 0)
                total += m[i];
        }
    }

    printf("%d\n", total);
    return 0;
}

测试用例 #

• 测试用例1：

  n = 3
  p[n] = 1 2 3
  m[n] = 10 4 12
  Output = 0
  

• 测试用例2：

  n = 4
  p[n] = 1 1 1 1
  m[n] = 10 12 13 20
  Output = 35
  

• 测试用例3：

  n = 5
  p[n] = 3 2 2 1 5
  m[n] = 4 4 3 3 2
  Output = 3
  

内容的提问来源于stack exchange，提问作者Dalton Gomes