(C卷,200分)- 可以处理的最大任务数（Java & JS & Python & C）

题目描述

在某个项目中有多个任务（用task数组表示）需要你进行处理，其中：

• task[i] = [si, ei]

你可以在 si ≤ day ≤ ei 中的任意一天处理该任务，请返回你可以处理的最大任务数。

输入描述

第一行为任务数量 n

• 1 ≤ n ≤ 100000

后面 n 行表示各个任务的开始时间和终止时间，使用 si，ei 表示

• 1 ≤ si ≤ ei ≤ 100000

输出描述

输出为一个整数，表示可以处理的最大任务数。

用例

题目解析

本题可以利用贪心思维+优先队列来求解。

我们可以将所有任务时间区间按照：优先按照结束时间降序，如果结束时间相同，则按照开始时间降序。这样排序的原因如下：

首先，任务优先按照结束时间降序后，那么第一个任务的结束时间就是最晚的（最大的），此时我们可以让第一个任务就在最晚时刻执行，如下面例子：

3
1 4
2 3
1 2

按照结束时间降序后：[1,4] , [2, 3],  [1, 2] ，第一个任务[1,4]在时刻4执行

这样做的好处是，避免第一个任务抢夺后面任务的执行时间，如下图所示：

• 如果第一个任务在时刻4执行，则第二个任务就有两个选择，时刻2或时刻3

• 如果第一个任务在时刻3执行，则第二个任务就只有一个选择，只能在时刻2执行

如果存在多个任务的结束时间都相同的话，则还需要对这些任务按照开始时间降序，这么做的原因是：

• "时间长" 的任务 "可选执行时刻" 多
• "时间短" 的任务 "可选执行时刻" 少

因此应该优先让时间跨度短的任务先执行，如下图所示：

• 如果优先时间短的任务，则三个任务都能执行

• 如果优先时间长的任务，则只能执行两个任务

但是上面逻辑是存在问题的，请看下面图示：

此时按照前面逻辑的话，只能执行三个任务

但是其实可以执行四个任务，执行策略如下：

主要问题是，当我们按照结束时间降序后，第一个任务选择时刻8执行完，此时后面三个任务的截止时间其实都是相同的，变为了时刻7。

因此，此时我们应该对后面三个任务重新按照时间跨度降序，再优先执行短的任务。

本题数量级较大，因此如果每次执行完一个任务，都对剩余任务进行更新结束时间，并重新排序的话，会超时。

改进策略是，使用优先队列，即：

如果当前任务的结束时间end >= 上一个任务的执行时刻last_end，则更新当前任务的结束为last_end – 1。如果 last_end – 1 > 当前任务开始时间start，则将当前任务重新入队排优先级。否则当前任务不可执行。

Java和Python有内置的优先队列类，而JS和C没有，因此JS和C需要手动实现一个优先队列，关于优先队列的实现原理请看：

经过测试，下面逻辑在本题数量级下会超时：

如果当前任务的结束时间end >= 上一个任务的执行时刻last_end，则更新当前任务的结束为last_end – 1。如果 last_end – 1 > 当前任务开始时间start，则将当前任务重新入队排优先级。否则当前任务不可执行。

因为，我们需要频繁更新任务的结束时间，并且入队出队。

为了避免频繁的更新任务结束时间，以及入队出队，我们可以做如下改动：

1、统计输入的所有任务的时间段，仅按照结束时间降序，得到数组ranges

2、定义一个优先队列pq，仅用于保存任务的开始时间（开始时间越大，优先级越高），我们可以认为优先队列中保存的任务（的开始时间）对应的结束时间都是相同的，我们定义这个公共结束时间为pq_end

3、遍历ranges，得到每一个任务的开始，结束时间range：[start, end]，然后比较遍历到任务的end 和 优先队列中所有任务的公共结束时间pq_end：

• 如果 end < pq_end，则在end ~ pq_end 这段间隔时间内，我们可以从pq中挑选出pq_end – end 个 较短任务进行执行，执行前需要检查 对应任务的开始时间 start <= pq_end，若不满足则不执行。每执行一个任务，则pq_end -= 1，count += 1（count是已执行的任务数量）。当pq_end == end时，则将当前遍历的任务的start 加入 优先队列。

具体过程如下图所示：

JS算法源码

超时解法，但是好理解，是下一种解法的基础

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const n = parseInt(await readline());

  // 结束时间越大（越晚）优先级越高，结束时间相同时，开始时间越大（越晚）优先级越高
  const pq = new PriorityQueue((a, b) =>
    a.end != b.end ? b.end - a.end : b.start - a.start
  );

  for (let i = 0; i < n; i++) {
    const [start, end] = (await readline()).split(" ").map(Number);
    pq.offer(new Range(start, end));
  }

  // 记录最大任务数
  let count = 0;

  // 记录上一个任务的执行时刻
  let last_end = Infinity;

  while (pq.size() > 0) {
    const range = pq.poll();

    if (range.end < last_end) {
      // 当前任务结束时刻end < 上个任务结束时刻last_end，则当前任务选择在end时刻执行
      last_end = range.end;
      count++;
    } else if (last_end > range.start) {
      // 当前任务结束时刻end ≥ 上个任务结束时刻last_end，则更新当前任务的结束时间为last_end-1，后重新加入优先队列排队
      // 同时注意range新的结束时间last_end - 1不能小于range.start，否则该任务无法执行
      range.end = last_end - 1;
      pq.offer(range);
    }
  }

  console.log(count);
})();

class Range {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}

// 基于堆实现优先队列
class PriorityQueue {
  constructor(cpr) {
    this.queue = [];
    this.cpr = cpr;
  }

  swap(a, b) {
    const tmp = this.queue[a];
    this.queue[a] = this.queue[b];
    this.queue[b] = tmp;
  }

  // 上浮
  swim() {
    let c = this.queue.length - 1;

    while (c >= 1) {
      const f = Math.floor((c - 1) / 2);

      if (this.cpr(this.queue[c], this.queue[f]) < 0) {
        this.swap(c, f);
        c = f;
      } else {
        break;
      }
    }
  }

  // 入队
  offer(val) {
    this.queue.push(val);
    this.swim();
  }

  // 下沉
  sink() {
    let f = 0;

    while (true) {
      let c1 = 2 * f + 1;
      let c2 = c1 + 1;

      let c;
      let val1 = this.queue[c1];
      let val2 = this.queue[c2];
      if (val1 != undefined && val2 != undefined) {
        c = this.cpr(val1, val2) < 0 ? c1 : c2;
      } else if (val1 != undefined) {
        c = c1;
      } else if (val2 != undefined) {
        c = c2;
      } else {
        break;
      }

      if (this.cpr(this.queue[c], this.queue[f]) < 0) {
        this.swap(c, f);
        f = c;
      } else {
        break;
      }
    }
  }

  // 出队
  poll() {
    this.swap(0, this.queue.length - 1);
    const res = this.queue.pop();
    this.sink();
    return res;
  }

  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }
}

不超时解法

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const n = parseInt(await readline());

  const ranges = [];
  for (let i = 0; i < n; i++) {
    ranges.push((await readline()).split(" ").map(Number));
  }

  // 将所有任务按照结束时间降序
  ranges.sort((a, b) => b[1] - a[1]);

  // 优先队列中记录的是任务的开始时间，并且开始时间越大，优先级越高
  const pq = new PriorityQueue((a, b) => b - a);

  // 优先队列中记录的是结束时间相同的任务的开始时间，pq_end就是优先队列中任务的相同结束时间
  let pq_end = Infinity;

  // 最大任务数
  let count = 0;

  // 当前任务的开始和结束时间
  for (let [start, end] of ranges) {
    // 如果当前任务的结束时间 小于 优先队列中记录的任务的结束时间，则两个结束时间之间的间隔时间段，可以处理一些紧急任务
    while (pq.size() > 0 && end < pq_end) {
      // 这里的紧急任务即指时间短的任务，即开始时间比较大的任务
      if (pq.poll() <= pq_end) {
        // 如果紧急任务的开始时间未超过其结束时间，则可以执行
        count++;
        pq_end--; // 一个时刻只执行一个任务
      }
    }

    // 间隔时间消耗完后，优先队列中的任务的结束时间全部更新为当前任务的结束时间
    pq.offer(start);
    pq_end = end;
  }

  // 收尾处理
  while (pq.size() > 0) {
    if (pq.poll() <= pq_end) {
      count++;
      pq_end--;
    }
  }

  console.log(count);
})();

// 基于堆实现优先队列
class PriorityQueue {
  constructor(cpr) {
    this.queue = [];
    this.cpr = cpr;
  }

  swap(a, b) {
    const tmp = this.queue[a];
    this.queue[a] = this.queue[b];
    this.queue[b] = tmp;
  }

  // 上浮
  swim() {
    let c = this.queue.length - 1;

    while (c >= 1) {
      const f = Math.floor((c - 1) / 2);

      if (this.cpr(this.queue[c], this.queue[f]) < 0) {
        this.swap(c, f);
        c = f;
      } else {
        break;
      }
    }
  }

  // 入队
  offer(val) {
    this.queue.push(val);
    this.swim();
  }

  // 下沉
  sink() {
    let f = 0;

    while (true) {
      let c1 = 2 * f + 1;
      let c2 = c1 + 1;

      let c;
      let val1 = this.queue[c1];
      let val2 = this.queue[c2];
      if (val1 != undefined && val2 != undefined) {
        c = this.cpr(val1, val2) < 0 ? c1 : c2;
      } else if (val1 != undefined) {
        c = c1;
      } else if (val2 != undefined) {
        c = c2;
      } else {
        break;
      }

      if (this.cpr(this.queue[c], this.queue[f]) < 0) {
        this.swap(c, f);
        f = c;
      } else {
        break;
      }
    }
  }

  // 出队
  poll() {
    this.swap(0, this.queue.length - 1);
    const res = this.queue.pop();
    this.sink();
    return res;
  }

  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }
}

Java算法源码

超时解法，但是好理解，是下一种解法的基础

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  static class Range {
    int start;
    int end;

    public Range(int start, int end) {
      this.start = start;
      this.end = end;
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    // 结束时间越大（越晚）优先级越高，结束时间相同时，开始时间越大（越晚）优先级越高
    PriorityQueue<Range> pq =
        new PriorityQueue<>((a, b) -> a.end != b.end ? b.end - a.end : b.start - a.start);

    for (int i = 0; i < n; i++) {
      pq.offer(new Range(sc.nextInt(), sc.nextInt()));
    }

    // 记录最大任务数
    int count = 0;

    // 记录上一个任务的执行时刻
    int last_end = Integer.MAX_VALUE;

    while (pq.size() > 0) {
      Range range = pq.poll();

      if (range.end < last_end) {
        // 当前任务结束时刻end < 上个任务结束时刻last_end，则当前任务选择在end时刻执行
        last_end = range.end;
        count++;
      } else if (last_end > range.start) {
        // 当前任务结束时刻end ≥ 上个任务结束时刻last_end，则更新当前任务的结束时间为last_end-1，后重新加入优先队列排队
        // 同时注意range新的结束时间last_end - 1不能小于range.start，否则该任务无法执行
        range.end = last_end - 1;
        pq.offer(range);
      }
    }

    System.out.println(count);
  }
}

不超时解法

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[][] ranges = new int[n][2];
    for (int i = 0; i < n; i++) {
      ranges[i][0] = sc.nextInt();
      ranges[i][1] = sc.nextInt();
    }

    // 将所有任务按照结束时间降序
    Arrays.sort(ranges, (a, b) -> b[1] - a[1]);

    // 优先队列中记录的是任务的开始时间，并且开始时间越大，优先级越高
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

    // 优先队列中记录的是结束时间相同的任务的开始时间，pq_end就是优先队列中任务的相同结束时间
    int pq_end = Integer.MAX_VALUE;

    // 最大任务数
    int count = 0;

    for (int[] range : ranges) {
      // 当前任务的开始和结束时间
      int start = range[0];
      int end = range[1];

      // 如果当前任务的结束时间 小于 优先队列中记录的任务的结束时间，则两个结束时间之间的间隔时间段，可以处理一些紧急任务
      while (pq.size() > 0 && end < pq_end) {
        // 这里的紧急任务即指时间短的任务，即开始时间比较大的任务
        if (pq.poll() <= pq_end) {
          // 如果紧急任务的开始时间未超过其结束时间，则可以执行
          count++;
          pq_end--; // 一个时刻只执行一个任务
        }
      }

      // 间隔时间消耗完后，优先队列中的任务的结束时间全部更新为当前任务的结束时间
      pq.add(start);
      pq_end = end;
    }

    // 收尾处理
    while (pq.size() > 0) {
      if (pq.poll() <= pq_end) {
        count++;
        pq_end--;
      }
    }

    System.out.println(count);
  }
}

Python算法源码

超时解法，但是好理解，是下一种解法的基础

import heapq
import sys


class Range:
    def __init__(self, start, end):
        self.start = start
        self.end = end

    # 结束时间越大（越晚）优先级越高，结束时间相同时，开始时间越大（越晚）优先级越高
    def __gt__(self, other):
        if self.end != other.end:
            return other.end > self.end
        else:
            return other.start > self.start


# 输入获取
n = int(input())

pq = []
for _ in range(n):
    start, end = map(int, input().split())
    heapq.heappush(pq, Range(start, end))


# 算法入口
def getResult():
    # 记录最大任务数
    count = 0

    # 记录上一个任务的执行时刻
    last_end = sys.maxsize

    while len(pq) > 0:
        ran = heapq.heappop(pq)

        if ran.end < last_end:
            # 当前任务结束时刻end < 上个任务结束时刻last_end，则当前任务选择在end时刻执行
            last_end = ran.end
            count += 1
        elif last_end > ran.start:
            # 当前任务结束时刻end ≥ 上个任务结束时刻last_end，则更新当前任务的结束时间为last_end-1，后重新加入优先队列排队
            # 同时注意range新的结束时间last_end - 1不能小于range.start，否则该任务无法执行
            ran.end = last_end - 1
            heapq.heappush(pq, ran)

    return count


# 算法调用
print(getResult())

不超时解法

import heapq
import sys

# 输入获取
n = int(input())
ranges = [list(map(int, input().split())) for _ in range(n)]


# 算法入口
def getResult():
    # 将所有任务按照结束时间降序
    ranges.sort(key=lambda x: -x[1])

    # 优先队列中记录的是任务的开始时间，并且开始时间越大，优先级越高
    # 由于heapq默认是数值越小，优先级越大，因此这里存入负数的开始时间到pq
    pq = []

    # 优先队列中记录的是结束时间相同的任务的开始时间，pq_end就是优先队列中任务的相同结束时间
    pq_end = sys.maxsize

    # 最大任务数
    count = 0

    # 当前任务的开始和结束时间
    for start, end in ranges:
        # 如果当前任务的结束时间 小于 优先队列中记录的任务的结束时间，则两个结束时间之间的间隔时间段，可以处理一些紧急任务
        while len(pq) > 0 and end < pq_end:
            # 这里的紧急任务即指时间短的任务，即开始时间比较大的任务
            if -heapq.heappop(pq) <= pq_end:
                # 如果紧急任务的开始时间未超过其结束时间，则可以执行
                count += 1
                pq_end -= 1  # 一个时刻只执行一个任务

        # 间隔时间消耗完后，优先队列中的任务的结束时间全部更新为当前任务的结束时间
        heapq.heappush(pq, -start)
        pq_end = end

    # 收尾处理
    while len(pq) > 0:
        if -heapq.heappop(pq) <= pq_end:
            count += 1
            pq_end -= 1

    return count


# 算法调用
print(getResult())

C算法源码

超时解法，但是好理解，是下一种解法的基础

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* 任务时间段 */
typedef struct {
    int start;
    int end;
} Range;

Range* new_Range(int start, int end) {
    Range* range = (Range*) malloc(sizeof(Range));
    range->start = start;
    range->end = end;
    return range;
}

typedef Range E;

/* 优先队列实现 */
typedef struct PriorityQueue {
    E **arr;
    int size;
    int (*cmp)(const void *, const void *);
} PQ;

PQ *new_PQ(int capacity, int (*cmp)(const void *, const void *)) {
    PQ *pq = (PQ *) malloc(sizeof(PQ));
    pq->arr = (E **) malloc(sizeof(E *) * capacity);
    pq->size = 0;
    pq->cmp = cmp;
    return pq;
}

void swap_PQ(PQ *pq, int a, int b) {
    E *tmp = pq->arr[a];
    pq->arr[a] = pq->arr[b];
    pq->arr[b] = tmp;
}

// 上浮
void swim_PQ(PQ *pq) {
    int c = pq->size - 1;

    while (c >= 1) {
        int f = (c - 1) / 2;

        if (pq->cmp(pq->arr[c], pq->arr[f]) < 0) {
            swap_PQ(pq, c, f);
            c = f;
        } else {
            break;
        }
    }
}

// 入队
void offer_PQ(PQ *pq, E *val) {
    pq->arr[pq->size++] = val;
    swim_PQ(pq);
}

// 下沉
void sink_PQ(PQ *pq) {
    int f = 0;

    while (1) {
        int c1 = 2 * f + 1;
        int c2 = c1 + 1;

        int c;

        if (pq->size > c1 && pq->size > c2) {
            if (pq->cmp(pq->arr[c1], pq->arr[c2]) < 0) {
                c = c1;
            } else {
                c = c2;
            }
        } else if (pq->size > c1 && pq->size <= c2) {
            c = c1;
        } else if (pq->size <= c1 && pq->size > c2) {
            c = c2;
        } else {
            break;
        }

        if (pq->cmp(pq->arr[c], pq->arr[f]) < 0) {
            swap_PQ(pq, c, f);
            f = c;
        } else {
            break;
        }
    }
}

// 出队
E *poll_PQ(PQ *pq) {
    swap_PQ(pq, 0, pq->size - 1);
    E *res = pq->arr[--pq->size];
    sink_PQ(pq);
    return res;
}

int cmp(const void *a, const void *b) {
    Range *A = (Range *) a;
    Range *B = (Range *) b;
    // 结束时间越大（越晚）优先级越高，结束时间相同时，开始时间越大（越晚）优先级越高
    return A->end != B->end ? B->end - A->end : B->start - A->start;
}

int main() {
    int n;
    scanf("%d", &n);

    // 结束时间越大（越晚）优先级越高，结束时间相同时，开始时间越大（越晚）优先级越高
    PQ* pq = new_PQ(n, cmp);

    for (int i = 0; i < n; i++) {
        int start, end;
        scanf("%d %d", &start, &end);
        offer_PQ(pq, new_Range(start, end));
    }

    // 记录最大任务数
    int count = 0;

    // 记录上一个任务的执行时刻
    int last_end = INT_MAX;

    while (pq->size > 0) {
        Range* range = poll_PQ(pq);

        if (range->end < last_end) {
            // 当前任务结束时刻end < 上个任务结束时刻last_end，则当前任务选择在end时刻执行
            last_end = range->end;
            count++;
        } else if (last_end > range->start) {
            // 当前任务结束时刻end ≥ 上个任务结束时刻last_end，则更新当前任务的结束时间为last_end-1，后重新加入优先队列排队
            // 同时注意range新的结束时间last_end - 1不能小于range.start，否则该任务无法执行
            range->end = last_end - 1;
            offer_PQ(pq, range);
        }
    }

    printf("%dn", count);

    return 0;
}

不超时解法

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef int E;

/* 优先队列实现 */
typedef struct PriorityQueue {
    E *arr;
    int size;

    int (*cmp)(E, E);
} PQ;

PQ *new_PQ(int capacity, int (*cmp)(E, E)) {
    PQ *pq = (PQ *) malloc(sizeof(PQ));
    pq->arr = (E *) malloc(sizeof(E) * capacity);
    pq->size = 0;
    pq->cmp = cmp;
    return pq;
}

void swap_PQ(PQ *pq, int a, int b) {
    E tmp = pq->arr[a];
    pq->arr[a] = pq->arr[b];
    pq->arr[b] = tmp;
}

// 上浮
void swim_PQ(PQ *pq) {
    int c = pq->size - 1;

    while (c >= 1) {
        int f = (c - 1) / 2;

        if (pq->cmp(pq->arr[c], pq->arr[f]) < 0) {
            swap_PQ(pq, c, f);
            c = f;
        } else {
            break;
        }
    }
}

// 入队
void offer_PQ(PQ *pq, E val) {
    pq->arr[pq->size++] = val;
    swim_PQ(pq);
}

// 下沉
void sink_PQ(PQ *pq) {
    int f = 0;

    while (1) {
        int c1 = 2 * f + 1;
        int c2 = c1 + 1;

        int c;

        if (pq->size > c1 && pq->size > c2) {
            if (pq->cmp(pq->arr[c1], pq->arr[c2]) < 0) {
                c = c1;
            } else {
                c = c2;
            }
        } else if (pq->size > c1 && pq->size <= c2) {
            c = c1;
        } else if (pq->size <= c1 && pq->size > c2) {
            c = c2;
        } else {
            break;
        }

        if (pq->cmp(pq->arr[c], pq->arr[f]) < 0) {
            swap_PQ(pq, c, f);
            f = c;
        } else {
            break;
        }
    }
}

// 出队
E poll_PQ(PQ *pq) {
    swap_PQ(pq, 0, pq->size - 1);
    E res = pq->arr[--pq->size];
    sink_PQ(pq);
    return res;
}

int cmp(const void *a, const void *b) {
    int *A = (int *) a;
    int *B = (int *) b;
    return B[1] - A[1];
}

int cmp_PQ(int a, int b) {
    return b - a;
}

int main() {
    int n;
    scanf("%d", &n);

    int ranges[n][2];
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &ranges[i][0], &ranges[i][1]);
    }

    // 将所有任务按照结束时间降序
    qsort(ranges, n, sizeof(ranges[0]), cmp);

    // 优先队列中记录的是任务的开始时间，并且开始时间越大，优先级越高
    PQ *pq = new_PQ(n, cmp_PQ);

    // 优先队列中记录的是结束时间相同的任务的开始时间，pq_end就是优先队列中任务的相同结束时间
    int pq_end = INT_MAX;

    // 记录最大任务数
    int count = 0;


    for (int i = 0; i < n; i++) {
        // 当前任务的开始和结束时间
        int start = ranges[i][0];
        int end = ranges[i][1];

        // 如果当前任务的结束时间 小于 优先队列中记录的任务的结束时间，则两个结束时间之间的间隔时间段，可以处理一些紧急任务
        while (pq->size > 0 && end < pq_end) {
            // 这里的紧急任务即指时间短的任务，即开始时间比较大的任务
            if (poll_PQ(pq) <= pq_end) {
                // 如果紧急任务的开始时间未超过其结束时间，则可以执行
                count++;
                pq_end--;// 一个时刻只执行一个任务
            }
        }

        // 间隔时间消耗完后，优先队列中的任务的结束时间全部更新为当前任务的结束时间
        offer_PQ(pq, start);
        pq_end = end;
    }

    // 收尾处理
    while (pq->size > 0) {
        if (poll_PQ(pq) <= pq_end) {
            count++;
            pq_end--;
        }
    }

    printf("%dn", count);

    return 0;
}