算法題 12:任務(wù)調(diào)度算法(美團(tuán)校招筆試題)

[題目]http://mp.weixin.qq.com/s/-cR07rHU91owk8nMOfhz9w

題目:任務(wù)調(diào)度在分布式調(diào)度系統(tǒng)中是一個很復(fù)雜很有挑戰(zhàn)的問題叠赐。這里我們考慮一個簡化的場景:假設(shè)一個中央調(diào)度機(jī),有n個相同的任務(wù)需要調(diào)度到m臺服務(wù)器上去執(zhí)行赛不。由于每臺服務(wù)器的配置不一樣罢洲,因此服務(wù)器執(zhí)行一個任務(wù)所花費的時間也不同。現(xiàn)在假設(shè)第i個服務(wù)器執(zhí)行一個任務(wù)需要的時間為t[i]。

例如:有2個執(zhí)行機(jī)a, b. 執(zhí)行一個任務(wù)分別需要7min耸峭,10min,有6個任務(wù)待調(diào)度抓艳。如果平分這6個任務(wù)帚戳,即a,b各分三個任務(wù)偏友,則最短需要30min執(zhí)行完所有对供。如果a分這4個任務(wù),b分2個鹅髓,則最短28min執(zhí)行完京景。

請設(shè)計調(diào)度算法,使得所有任務(wù)完成所需的時間最短

  1. 簡述思路

  2. 請用你熟悉的編程語言編碼實現(xiàn)以下方法醒串,輸入為m臺服務(wù)器鄙皇,每臺機(jī)器處理一個任務(wù)的時間為t[i],完成n個任務(wù)伴逸,輸出n個任務(wù)在m臺服務(wù)器的分布:

int estimate_process_time(int[] t, int m, int n);

思路:本題是個基本的題型,考慮到如何進(jìn)行調(diào)度的問題博烂,調(diào)度問題是個非常大的問題漱竖,本題簡化了模型馍惹,該某型考慮的是如何組織計算單元, 使得計算的總時間最小悼吱。

其實良狈,學(xué)習(xí)算法直到現(xiàn)在,我基本上完成了算法的前半部分(基礎(chǔ))遇西,就是如何去思考一個算法題,用什么行為去完成這個算法粱檀,我對后半部分漫玄,比如圖論算法,DNF算法渗常,數(shù)論算法等等汗盘,這些高級算法我還是沒有掌握,還有就是如何進(jìn)行算法分析尸执,這個內(nèi)容我也沒有掌握缓醋,很遺憾,我需要學(xué)習(xí)的東西還有很多褪贵。個人感覺計算機(jī)的知識是個很龐大的體系,要想全部掌握我想很困難脆丁,所以針對個人興趣动雹,研究某一領(lǐng)域的算法是一個不錯的選擇,但是歼培,基礎(chǔ)的算法還是要會的,畢竟萬變不離其宗躲庄。

此題,如果能想到使用小頂堆笋庄,基本上就算完成了算法了倔监。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct nt{
    int n;
    int t;
    int i;
    nt (int e1, int e2) : n(0), t(e1), i(e2) {}
};

class CCompNt 
{
public:
    bool operator() (nt e1, nt e2) 
    {
        return (e2.n+1) * e2.t < (e1.n+1) * e1.t 
            || ((e2.n+1) * e2.t == (e1.n+1) * e1.t && e2.t <= e1.t);
    }
} CompNt;

class CCompNt2 
{
public:
    bool operator() (nt e1, nt e2) 
    {
        return e1.i < e2.i;
    }
} CompNt2;

void printNt(nt e)
{
    cout << "(" << e.i << "," << e.t << "," << e.n << ") ";
}

vector<nt> estimate_process_time(const vector<int> & vect, int m, int n)
{
    vector<nt> vecNt;
    for (int i=0; i<m; ++i) {
        vecNt.push_back(nt(vect[i], i));
    }

    make_heap(vecNt.begin(), vecNt.end(), CompNt);

    for (int i=0; i<n; ++i) {
        pop_heap(vecNt.begin(), vecNt.end(), CompNt);
        auto nt1 = vecNt.back();
        vecNt.pop_back();
        
        nt1.n += 1;
        vecNt.push_back(nt1);
        push_heap(vecNt.begin(), vecNt.end(), CompNt);
    }

    sort(vecNt.begin(), vecNt.end(), CompNt);

    return vecNt;
}

int main(int argc, char ** argv)
{
    int n = 6;
    int m = 2;
    vector<int> t = {
        7, 10
    };

    auto vecNt = estimate_process_time(t, m, n);

    cout << "(index, t, n)" << endl;
    for_each(vecNt.begin(), vecNt.end(), printNt);

    return 0;
}

文章的最后丐枉,還是想吐槽一下,C語言提供的數(shù)據(jù)結(jié)構(gòu)真心的少籍嘹,C++這方面做的不錯弯院,但是C++這方面需要不斷的訓(xùn)練和學(xué)習(xí),比如颂碘,這里設(shè)計小頂堆的時候椅挣,我對于比較算法的設(shè)計就出現(xiàn)了問題,糾結(jié)了好長時間鼠证。另外,這只是一個校招題适掰,題目的難度你們可以從代碼中感受一下荠列,代碼真的不難,難得是如何去想费就、去解決類似這樣的問題4ǘ印?寻帷艳汽!核心算法就是函數(shù)estimate_process_time中的for循環(huán)河狐,如果你用C實現(xiàn)瑟捣,那么heap的實現(xiàn)應(yīng)該也算是核心代碼了,這樣增加了解題的難度捐祠!

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末桑李,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子率拒,更是在濱河造成了極大的恐慌禁荒,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件勃痴,死亡現(xiàn)場離奇詭異热康,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)污它,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門庶弃,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人固惯,你說我怎么就攤上這事缴守≌蚧裕” “怎么了贴捡?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵烂斋,是天一觀的道長。 經(jīng)常有香客問我汛骂,道長,這世上最難降的妖魔是什么淑掌? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任抛腕,我火速辦了婚禮,結(jié)果婚禮上兽埃,老公的妹妹穿的比我還像新娘适袜。我一直安慰自己,他們只是感情好售貌,可當(dāng)我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布疫萤。 她就那樣靜靜地躺著,像睡著了一般恒削。 火紅的嫁衣襯著肌膚如雪尾序。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天携丁,我揣著相機(jī)與錄音兰怠,去河邊找鬼李茫。 笑死肥橙,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的娜庇。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼藕溅!你這毒婦竟也來了继榆?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤集币,失蹤者是張志新(化名)和其女友劉穎翠忠,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體秽之,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡考榨,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了冀惭。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片掀鹅。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖溃槐,靈堂內(nèi)的尸體忽然破棺而出科吭,到底是詐尸還是另有隱情猴鲫,我是刑警寧澤谣殊,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站宜狐,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏抚恒。R本人自食惡果不足惜络拌,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望混萝。 院中可真熱鬧萍恕,春花似錦、人聲如沸允粤。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽阔挠。三九已至,卻和暖如春购撼,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背迂求。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留毫玖,地道東北人。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓烹玉,卻偏偏與公主長得像阐滩,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子掂榔,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容

  • Spring Cloud為開發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見模式的工具(例如配置管理装获,服務(wù)發(fā)現(xiàn),斷路器穴豫,智...
    卡卡羅2017閱讀 134,716評論 18 139
  • 1. Java基礎(chǔ)部分 基礎(chǔ)部分的順序:基本語法绩郎,類相關(guān)的語法翁逞,內(nèi)部類的語法,繼承相關(guān)的語法挖函,異常的語法,線程的語...
    子非魚_t_閱讀 31,665評論 18 399
  • 1津畸,增加依賴:spring-boot-configuration-processor 2,@Configurati...
    firehole閱讀 306評論 0 0
  • 一夜寒流來襲肉拓,憔悴了顏容梳庆。風(fēng)流燕過,花落云舒膏执,眷戀間,卻難留相思更米。 兩端苦痛閑在,夢里心牽連。...
    之亦夫閱讀 255評論 0 0
  • 1消请,石嘴山銀行開戶瘤旨。 2,整理城邦和振寧材料存哲,開通網(wǎng)上銀行。 3祟偷,建行手機(jī)銀行開通,支付不限額修肠。 4,明達(dá)賬務(wù)處理...
    方一塵閱讀 185評論 0 0