30703：最少资源数量

题目

给定半开时间区间任务，求同时运行所需的最少资源数量。结束时刻等于下一任务开始时刻时，资源可以立即复用。

解析

先完整检查所有区间，再按开始时刻排序。处理任务前，把所有结束时刻 <= start 的资源从最小堆移除；堆中剩余数量就是当前并发数。堆的最大大小就是答案。因为排序发生在所有检查之后，参数错误不会修改任务数组。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct {
    int64_t start;
    int64_t end;
} ResourceTask;

static int compare_tasks(const void *left, const void *right) {
    const ResourceTask *a = left;
    const ResourceTask *b = right;
    if (a->start < b->start) {
        return -1;
    }
    if (a->start > b->start) {
        return 1;
    }
    if (a->end < b->end) {
        return -1;
    }
    if (a->end > b->end) {
        return 1;
    }
    return 0;
}

static void swap_i64(int64_t *left, int64_t *right) {
    int64_t temporary = *left;
    *left = *right;
    *right = temporary;
}

static void end_sift_down(
    int64_t *heap,
    size_t size,
    size_t index
) {
    for (;;) {
        size_t smallest = index;
        if (index < size / 2) {
            size_t left = index * 2 + 1;
            size_t right = left + 1;
            if (heap[left] < heap[smallest]) {
                smallest = left;
            }
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }
        }
        if (smallest == index) {
            return;
        }
        swap_i64(&heap[index], &heap[smallest]);
        index = smallest;
    }
}

static void end_push(int64_t *heap, size_t *size, int64_t value) {
    size_t index = (*size)++;
    heap[index] = value;
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (heap[parent] <= heap[index]) {
            return;
        }
        swap_i64(&heap[parent], &heap[index]);
        index = parent;
    }
}

static void end_pop(int64_t *heap, size_t *size) {
    --*size;
    if (*size > 0) {
        heap[0] = heap[*size];
        end_sift_down(heap, *size, 0);
    }
}

bool minimum_resource_count(
    ResourceTask *tasks,
    size_t count,
    size_t *out_resources
) {
    if (out_resources == NULL || (count > 0 && tasks == NULL)) {
        return false;
    }
    for (size_t i = 0; i < count; ++i) {
        if (tasks[i].start >= tasks[i].end) {
            return false;
        }
    }
    if (count == 0) {
        *out_resources = 0;
        return true;
    }
    if (count > SIZE_MAX / sizeof(int64_t)) {
        return false;
    }
    int64_t *ends = malloc(count * sizeof *ends);
    if (ends == NULL) {
        return false;
    }
    qsort(tasks, count, sizeof *tasks, compare_tasks);
    size_t heap_size = 0;
    size_t maximum = 0;
    for (size_t i = 0; i < count; ++i) {
        while (heap_size > 0 && ends[0] <= tasks[i].start) {
            end_pop(ends, &heap_size);
        }
        end_push(ends, &heap_size, tasks[i].end);
        if (heap_size > maximum) {
            maximum = heap_size;
        }
    }
    free(ends);
    *out_resources = maximum;
    return true;
}

排序为 $O(n\log n)$，每个结束时刻至多入堆和出堆一次，整体时间复杂度为 $O(n\log n)$，额外空间为 $O(n)$。