讨论/面试考题/一个任务调度的问题/
一个任务调度的问题

一个理发师理发的问题:理发店有 mm 个理发师,每个理发师完成一位顾客理发的时间不同
当有 nn 个顾客同时上门时,问最快的理发时间是多久?
测试用例:output m=3 m1=1 , m2=2 , m3 =3; n=3 output: time=2

刚开始刷题的菜鸟,没什么经验 T^T , 这种题目有什么思路么

展开讨论

比较容易想到的思路:每来一个新的顾客,优先分配给 "已理发时间" + "完成一个人理发的时间" 最少的理发师。
建立一个数组 cnt 来统计当前每个理发师已理发时间,初始化全 00,每来一个新顾客,遍历 cnt 数组和输入时间数组 t,寻找 cnt[j]+t[j] 最小的理发师 p,并将新顾客分配给他,更新 cnt 数组 cnt[p] += t[p] 和当前最大时间 ans
由于只需要控制理发时间最大者最小,只要找到满足 cnt[j]+t[j] <= ans 的理发师,就可以提前中止搜索,稍微节省一点时间。
两层循环,时间复杂度 O(mn)O(mn)mmnn 分别为理发师和顾客数量。

int minHaircutTime(vector<int> &t, int n) {
    int m = t.size();
    vector<int> cnt(m, 0);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int minTime = INT_MAX, p;
        for (int j = 0; j < m; j++) {
            if (cnt[j] + t[j] <= ans) {
                p = j;
                break;
            }
            if (cnt[j] + t[j] < minTime) {
                minTime = cnt[j] + t[j];
                p = j;
            }
        }
        cnt[p] += t[p];
        ans = max(ans, cnt[p]);
    }
    return ans;
}

另一个思路来自于上周双周赛最后一题「分享巧克力」的题解
用二分法在区间 [left,right][left, right] 查找最优解,对于每个解 xx,尝试进行顾客分配,分配时每个理发师的顾客数量不超过 x/t[j]x/t[j]。如果能够将 nn 个顾客分配完,说明该解可行,在左半段继续查找,否则在右半段查找。
初始区间可定为 [0,nt[0]][0, n*t[0]],最优解不会超过将所有顾客分配给一名理发师的时间。
二分时间复杂度 O(log(nt[0]))O(log(n*t[0])),检验解的时间复杂度 O(m)O(m),综合为 O(mlog(nt[0]))O(mlog(n*t[0])),一般来说 t[0]t[0] 比较小,这个复杂度比上面的要好。

int minHaircutTime(vector<int> &t, int n) {
    int left = 0, right = t[0]*n; //最优解不会超过将所有顾客分配给一个理发师的时间
    int ans = 0;
    while (left <= right) {
        int mid = (left+right)/2, cnt = n;
        for (int i = 0; i < t.size(); i++) {
            cnt -= mid/t[i];
            if (cnt <= 0) {
                // 当前解mid可行,向小的方向搜索
                ans = mid;
                right = mid - 1;
                break;
            }
        }
        if (cnt > 0) left = mid + 1; //当前解mid不可行,向大的方向搜索
    }
    return ans;
}
3
展开全部 2 讨论