2.5.20

2.5.20 #

解答 #

我们以事件为单位进行处理，每个事件包含任务名，记录时刻和开始/结束标记。

随后按照时间从小到大排序，遍历事件数组。

设开始的时候机器空闲，设置计数器，作为当前正在运行的任务数量。

当遇到开始事件时，计数器加一；遇到结束事件时，计数器减一。

如果计数器加一之前计数器为 0，说明空闲状态结束，记录并更新空闲时间，当前时间为忙碌开始的时间。

如果计数器减一之后计数器为 0，说明忙碌状态结束，记录并更新忙碌时间，当前时间为空闲开始的时间。

测试结果：

代码 #

var nowRunning = 0; // 正在运行的程序数量
var maxIdle = 0;
var maxBusy = 0;
var items = int.Parse(Console.ReadLine());
var jobs = new JobEvent[items * 2];
for (var i = 0; i < jobs.Length; i += 2)
{
    jobs[i] = new JobEvent();
    jobs[i + 1] = new JobEvent();

    jobs[i].IsFinished = false; // 开始事件
    jobs[i + 1].IsFinished = true; // 停止事件

    var record = Console.ReadLine().Split(new[] { ' ', ':' }, StringSplitOptions.RemoveEmptyEntries);
    jobs[i].JobName = record[0];
    jobs[i + 1].JobName = record[0];

    jobs[i].Time = int.Parse(record[1]) * 60 + int.Parse(record[2]);
    jobs[i + 1].Time = int.Parse(record[3]) * 60 + int.Parse(record[4]);
}

Array.Sort(jobs);

// 事件处理
var idleStart = 0;
var busyStart = 0;
for (var i = 0; i < jobs.Length; i++)
{
    // 启动事件
    if (!jobs[i].IsFinished)
    {
        // 空闲状态结束
        if (nowRunning == 0)
        {
            var idle = jobs[i].Time - idleStart;
            if (idle > maxIdle)
                maxIdle = idle;

            // 开始忙碌
            busyStart = jobs[i].Time;
        }

        nowRunning++;
    }
    else
    {
        nowRunning--;
        // 忙碌状态结束
        if (nowRunning == 0)
        {
            var busy = jobs[i].Time - busyStart;
            if (busy > maxBusy)
                maxBusy = busy;

            // 开始空闲
            idleStart = jobs[i].Time;
        }
    }
}

Console.WriteLine("Max Idle: " + maxIdle);
Console.WriteLine("Max Busy: " + maxBusy);

/// <summary>
/// 任务变化事件。
/// </summary>
internal class JobEvent : IComparable<JobEvent>
{
    public string JobName;
    public int Time;
    public bool IsFinished; // false = 开始，true = 结束

    public int CompareTo(JobEvent other)
    {
        return Time.CompareTo(other.Time);
    }
}