计算调度流程执行时间（100分） - 华为机试真题题解

题目描述

无线用户管理系统中，一个用户呼叫流程称为一个 task。task 由若干个子流程（Procedure）组成，Procedure 可以继续调用更小粒度的 Procedure；

task 是呼叫流程的入口，也是一种特殊的Procedure。

为了对呼叫流程处理性能进行优化分析，调度框架在每个Procedure的入口和出口记录了系统时间戳日志。现在需要你根据日志信息分析得到每个Procedure的实际执行时间（不包括子 procedure）。

备注：

• Procedure 可以被调用多次，也可以被递归调用;
• Procedure 的入口记录表示 Procedure 从记录时间戳的起始开始执行，出口记录表示 Procedure 从记录时间戳的末尾结束执行；
• Procedure 的日志时间截至少间隔1；
• 如里同一个 Procedure 多次调用且执行时间不相同，请输出最长的执行时间。

输入

第一行输入Procedure 的个数m和日志记录个数，以空格隔开。m取值范围[1, 100], n 取值范围 [2, 500]

后面的n行输入日志记录，每条日志由3个整数组成并以空格隔开。日志格式： Procedure编号（取值范围[0,m)）,日志类型（入口：0， 出口：1），时间戳（取值范围：[0: 1000000000]）

输出

以 Procedure 编号顺序输出每个 Procedure 的实际执行时间，以空格隔开；

示例1

输入：
2 6
0 0 0
1 0 2
1 1 5
1 0 6
1 1 9
0 1 10

输出：
3 4

示例2

输入：
2 6
0 0 0
1 0 2
1 0 5
1 1 10
1 1 11
0 1 12

输出：
3 6

解释： 
Procedure 0 在时间戳0开始执行，执行2个单位时间，于时间戳1的末尾结束执行。
Procedure 1 在时间戳2开始执行，执行3个单位时间，于时间戳4的末尾结束执行。
Procedure 1 在时间戳5开始递归调用自己（记为 Procedure 1'），执行6个单位时间，于时间戳10的末尾结束执行。
Procedure 1 在时间戳11开始恢复执行，执行1个单位时间。
Procedure 0 在时间戳12开始恢复执行，执行1个单位时间。
所以Procedure 0 总共执行 2 + 1 = 3 个单位时间，Procedure 1 总共执行 3 + 1 = 3 个单位时间。 Procedure 1' 总共执行6个单位时间。所以Procedure 1取最大值即6。

C++

[代码仅供学习参考并未进行大量数据测试]

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<int> times(m);
    // 用于暂存还没有执行完的子流程, 存储形式 pair<Procedure编号, Procedure执行总耗时>
    stack<pair<int, int>> st;
    for (int i = 0, last = 0, id, type, now; i < n; i++) {
        cin >> id >> type >> now;
        if (type == 0) { // 开始执行
            if (!st.empty()) {
                // 当前时间到上一个时间点属于栈顶的Procedure执行
                st.top().second += (now - last);
            }
            st.emplace(id, 0);
        } else {    // 结束执行
            now++;
            int tot = st.top().second + (now - last);
            st.pop();
            // 同一个 Procedure 多次调用且执行时间不相同，保留最长的执行时间
            times[id] = max(times[id], tot);
        }
        last = now;
    }

    // 输出每个 Procedure  的实际执行时间
    for (int i = 0; i < m; i++) {
        if (i) cout << " ";
        cout << times[i];
    }

    return 0;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏