有n個時間段 如下圖所示:
其中每個時間段不能與其他時間段交叉(如 時間段1:10:00:00-12:00:00,時間段2:10:30:00-13:00:00),或者不能被包含(如 時間段1:10:00:00-12:00:00,時間段2:07:30:00-20:00:00)
時間段的個數(shù)沒有限制,前后順序沒有限制。怎么處理比較高效呢?
現(xiàn)在通過sort 排序之后,比較下個時間段的開始時間 是否大于 當(dāng)前時間段的結(jié)束時間來處理。是否有更好的辦法解決呢?
排序后再比較這種操作的最后效率取決于你排序的效率了,一般都是O(nlogn),如果還想再快,那只能想O(n)復(fù)雜度的方法了。
方法1:O(n),需要看你的業(yè)務(wù)情況
假如時間都是半個小時一截的,一天24小時,可以分成48個半個小時,那么可以用長度為48的數(shù)組表示這半個小時是否被占用,0未占用 1占用,例如a = [1,1,0,...] 就表示00:00 ~ 00:30、00:30 ~ 01:00是占用的。如果你是一個內(nèi)存吝嗇型的人,那么可以考慮用位運算來表示時間占用情況。
這樣以來,遍歷到每一個元素直接查數(shù)組看是不是被占用了就行,時間復(fù)雜度是O(n)
方法2:最壞O(nlogn),二分 + 插入排序,比直接排序稍微好點
維持一個以開始時間有序的、無時間沖突的數(shù)組,判斷一個時間段a是否與現(xiàn)有安排沖突,先拿a的開始時間用二分法找插入位置,找到后與前后元素比較看是否沖突,不沖突的話就插入。這個算法最壞情況是每次都沒有沖突,這樣會導(dǎo)致每次都要把元素后挪,所以最壞情況下是O(nlogn),如果安排經(jīng)常沖突的話,這個算法是不錯的。
暫時只想到這2個
北大青鳥APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國家
達內(nèi)教育集團成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機構(gòu),是中國一站式人才培養(yǎng)平臺、一站式人才輸送平臺。2014年4月3日在美國成功上市,融資1
北大課工場是北京大學(xué)校辦產(chǎn)業(yè)為響應(yīng)國家深化產(chǎn)教融合/校企合作的政策,積極推進“中國制造2025”,實現(xiàn)中華民族偉大復(fù)興的升級產(chǎn)業(yè)鏈。利用北京大學(xué)優(yōu)質(zhì)教育資源及背
博為峰,中國職業(yè)人才培訓(xùn)領(lǐng)域的先行者
曾工作于聯(lián)想擔(dān)任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔(dān)任項目經(jīng)理從事移動互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍懿科技有限責(zé)任公司從事總經(jīng)理職務(wù)負責(zé)iOS教學(xué)及管理工作。
浪潮集團項目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺面向?qū)ο箝_發(fā)經(jīng)驗,技術(shù)功底深厚。 授課風(fēng)格 授課風(fēng)格清新自然、條理清晰、主次分明、重點難點突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫,具有快速界面開發(fā)的能力,對瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁制作和網(wǎng)頁游戲開發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開發(fā)經(jīng)驗。曾經(jīng)歷任德國Software AG 技術(shù)顧問,美國Dachieve 系統(tǒng)架構(gòu)師,美國AngelEngineers Inc. 系統(tǒng)架構(gòu)師。