華為機試題詳解：操作系統任務調度問題

問題背景與需求

在操作系統中，任務分為系統任務與用戶任務兩大類。系統任務優先級範圍為 0 ~ 49（數值越小優先級越高），用戶任務優先級範圍為 50 ~ 255。優先級大於 255 的任務視為非法，需剔除。給定一個任務隊列 task[]（長度 n，元素值為優先級），需實現 scheduler 函數，將合法任務按類型分離存入 system_task[] 與 user_task[]，並遵循以下規則：

• 同類任務按優先級從高到低排序（數值小者優先）
• 優先級相同時，按原隊列入隊順序排列（先入隊者優先）
• 陣列以 -1 結尾標識

範例說明

task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99}
// 系統任務優先級 < 50：0, 30, 1, 40 → 下標 0,1,3,7
// 用戶任務 50~255：155, 80, 170, 99 → 下標 2,4,6,8
// 300 為非法任務，剔除

system_task[] = {0, 3, 1, 7, -1}  // 優先級排序：0(0) > 1(1) > 30(3) > 40(7)
user_task[]   = {4, 8, 2, 6, -1}  // 優先級排序：80(4) > 99(8) > 155(2) > 170(6)

函數接口

void scheduler(int task[], int n, int system_task[], int user_task[]);

三種解法比較

解法一：多輪查找最小值法

在 task 中反覆查找最小、次最小值的下標，依次填入對應陣列。邏輯控制點較多，容易出錯，不推薦面試現場編寫。

解法二：插入排序法（推薦）

遍歷 task 一次，將每個合法任務下標按插入排序邏輯直接放入對應陣列，維持有序。邏輯清晰、易控制、時間複雜度 O(n²) 但在 n 較小（機試常見）時完全足夠。

解法三：結構體排序法

將 task 複製到結構體陣列（含優先級、下標、類型），快速排序後再分發。代碼量稍大，但擴展性強。

插入排序法核心代碼實現

void scheduler(int task[], int n, int system_task[], int user_task[]) {
    int syscount = 0, usercount = 0;

    for (int i = 0; i < n; i++) {
        int current = task[i];

        // 系統任務：0 <= priority < 50
        if (current >= 0 && current < 50) {
            system_task[syscount++] = i;  // 先放入末尾
            // 插入排序：從倒數第二個向前比較
            for (int j = syscount - 2; j >= 0; j--) {
                if (task[system_task[j]] > current) {
                    system_task[j + 1] = system_task[j];  // 後移
                } else {
                    break;  // 找到插入位置
                }
                system_task[j + 1] = i;  // 插入
            }
        }
        // 用戶任務：50 <= priority <= 255
        else if (current >= 50 && current <= 255) {
            user_task[usercount++] = i;
            for (int j = usercount - 2; j >= 0; j--) {
                if (task[user_task[j]] > current) {
                    user_task[j + 1] = user_task[j];
                } else {
                    break;
                }
                user_task[j + 1] = i;
            }
        }
        // 非法任務（>255 或 <0）直接忽略
    }
    system_task[syscount] = -1;
    user_task[usercount] = -1;
}

關鍵點總結

1. 邊界條件：嚴格檢查 0~49、50~255，其餘剔除。
2. 穩定性：插入排序天然穩定，滿足「同優先級按入隊順序」要求。
3. 下標存儲：陣列存的是原 task 下標，比較時需用 task[system_task[j]] 取優先級。
4. 結尾標記：最後務必加 -1，否則調用方無法判斷結束。

測試主函數

void taskprint(int system_task[], int user_task[], int n) {
    for (int i = 0; i < n; i++) {
        if (system_task[i] != -1) cout << system_task[i] << endl;
        else break;
    }
    for (int i = 0; i < n; i++) {
        if (user_task[i] != -1) cout << user_task[i] << endl;
        else break;
    }
}

int main() {
    int task[] = {0, 300, 400, 1, 80, 300, 170, 40, 99};
    int n = sizeof(task) / sizeof(int);
    int *system_task = new int[n + 1];
    int *user_task = new int[n + 1];
    scheduler(task, n, system_task, user_task);
    taskprint(system_task, user_task, n + 1);
    delete[] system_task;
    delete[] user_task;
    return 0;
}