剛開(kāi)始生怕題做不完，選擇題聽(tīng)說(shuō)去年是15分鐘20題，一頓亂選。

第一道選擇題 樹(shù)的前序遍歷35421，中序遍歷25431，

后序遍歷應(yīng)該是....? 這道題是不是有點(diǎn)問(wèn)題，沒(méi)敢仔細(xì)看就選了....

編程題更是血炸.....一道都不會(huì)。果然刷題不夠多，只看看劍指offer果然不管用啊....第一次筆試就這么拉了。

明天還有美團(tuán)的筆試，后天的匯報(bào)ppt還沒(méi)做呢，5555555555555555。

但還是先總結(jié)一下吧，編程題第一道。

1.客服人數(shù)

輸入一個(gè)n表示要輸入的通話記錄個(gè)數(shù)，接下來(lái)輸入n行，每行為逗號(hào)相隔的兩個(gè)整數(shù)，
兩個(gè)數(shù)字分別代表呼入時(shí)間和掛斷時(shí)間的時(shí)間戳。
舉例：10,30，表示[10,30)，代表第10秒呼入，第30秒已經(jīng)掛斷，
即第30秒可以接入新的來(lái)電； 每一行都是一條通話記錄，通話記錄已經(jīng)按呼入時(shí)間由小到大排序
輸出一個(gè)整數(shù)；代表最少需要多少客服，可以滿足所有旅客來(lái)電不用等待。

測(cè)試樣例：

6 0，30 0，50 10，20 15，30 20，50 20，65

樣例輸出：

5

之前沒(méi)有做過(guò)類(lèi)似的題，完全沒(méi)有思路，瞎寫(xiě)了點(diǎn)代碼，瞎貓撞上死耗子過(guò)了50%。

結(jié)束后在牛客看到大佬發(fā)答案，才知道leetcode 253跟本題高度重合....

這里貼出來(lái)找到的一個(gè)博主Java實(shí)現(xiàn)的代碼

https://blog.csdn.net/qq_41645636/article/details/99475054?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

始終還是缺少點(diǎn)解釋，腦子不靈光的我還是沒(méi)理解啊，帶著思考繼續(xù)找題解，下面這個(gè)博客講的不錯(cuò)

https://www.cnblogs.com/aaronliu1991/p/11774859.html

恍然大悟，其實(shí)本質(zhì)上是個(gè)很簡(jiǎn)單的問(wèn)題。

不管是會(huì)議室開(kāi)會(huì)也好，還是客服接電話也好，對(duì)于給定的多個(gè)時(shí)間段序列，需要找到最少的數(shù)量會(huì)議室或是客服，使得過(guò)程不會(huì)堵塞，抽象成數(shù)學(xué)問(wèn)題本質(zhì)上是同一個(gè)東西。

就按客服接電話這個(gè)問(wèn)題來(lái)講，在某個(gè)時(shí)間段客服接電話了，什么情況下會(huì)需要多增加一個(gè)客服，防止用戶(hù)等待呢？答案是下一個(gè)時(shí)段端與當(dāng)前客服時(shí)間段重合則需要增加一個(gè)客服。比如[5,10]一個(gè)客服，那么下一段如果是[9,12]必定需要增加一個(gè)客服，如果是[11,12]就不需要增加新的客服。

因?yàn)橹恍枰雷钌傩枰嗌倏头?#xff0c;因此可以單獨(dú)對(duì)每個(gè)時(shí)間段的開(kāi)始時(shí)間和結(jié)束時(shí)間進(jìn)行排序。

比如輸入[1,5],[4,7],[9,10],[2,3]，單獨(dú)對(duì)開(kāi)始時(shí)間和結(jié)束時(shí)間排序，得到如下

startArray=[1,2,4,9]? ?endArray=[3,5,7,10]，定義客服數(shù)量cnt=0.

然后從最小的開(kāi)始時(shí)間找，如果startArray[startIndex]大于當(dāng)前的結(jié)束時(shí)間endArray[endIndex]，說(shuō)明當(dāng)前不存在重合時(shí)間段，那么客服數(shù)量不需要增加；如果小于endArray[endIndex]，那么說(shuō)明存在重合時(shí)間段，需要增加一個(gè)客服。

（最開(kāi)始startIndex=0，stopIndex=0）當(dāng)然對(duì)于合法輸入，排序后的第一個(gè)開(kāi)始時(shí)間肯定小于第一個(gè)結(jié)束時(shí)間，因此stopIndex++，cnt++.

根據(jù)上面的輸入序列推一下：

1.startIndex=0，endIndex=0，cnt=0，此時(shí)1<3，==>startIndex++;cnt++

2.startIndex=1，endIndex=0，cnt=1，此時(shí)2<3，==>startIndex++;cnt++

3.startIndex=2，endIndex=0，cnt=2，此時(shí)4>3，==>endIndex++;

4.startIndex=2，endIndex=1，cnt=2，此時(shí)4<5，==>startIndex++;cnt++

5.startIndex=3，endIndex=1，cnt=3，此時(shí)9>5，==>endIndex++;

6.startIndex=3，endIndex=2，cnt=3，此時(shí)9>7，==>endIndex++;

7.startIndex=3，endIndex=3，cnt=3，此時(shí)9<10，==>startIndex++;cnt++

退出循環(huán) 最后cnt=3。

以上就是題解思路，關(guān)鍵代碼其實(shí)很少，但是好像確實(shí)有點(diǎn)繞，但是想明白了其實(shí)很簡(jiǎn)單....本人就被繞了一個(gè)晚上.....

下面貼出Java程序代碼實(shí)現(xiàn)（主函數(shù)是用來(lái)控制臺(tái)輸入的，看關(guān)鍵算法代碼即可）

public static void main(String[] args) {Scanner sc =new Scanner(System.in);int count =Integer.parseInt(sc.nextLine().trim());int[][] rows =new int[count][2];for(int i=0;i<count;i++){String row =sc.nextLine();String[] split = row.split(",");rows[i][0]=Integer.parseInt(split[0]);rows[i][1]=Integer.parseInt(split[1]);}int res=0;res = calcMinStaff(rows);System.out.println(String.valueOf(res));}static int calcMinStaff(int[][] rows) {//每一行保存一個(gè)時(shí)間段，現(xiàn)需要對(duì)所有的時(shí)間端做一個(gè)分割//所有的開(kāi)始時(shí)間放一起，所有的結(jié)束時(shí)間放一起//然后sortint[] startArray = new int[rows.length];int[] endArray =new int[rows.length];for(int i=0;i<rows.length;i++){startArray[i]=rows[i][0];endArray[i]=rows[i][1];}Arrays.sort(startArray);Arrays.sort(endArray);int cnt =0; //客服數(shù)量int eIndex=0;//算法關(guān)鍵for(int sIndex=0;sIndex<startArray.length;sIndex++){if(startArray[sIndex]<endArray[eIndex]){cnt++;//需要增加客服}else {eIndex++;//切換到下一個(gè)結(jié)束時(shí)間}}return cnt;}

牛客網(wǎng)的大佬用的貌似是貪心算法求解，看起來(lái)好像更能理解一點(diǎn)，地址如下：

https://www.nowcoder.com/discuss/398154?type=all&order=time&pos=&page=1

上面的代碼時(shí)間復(fù)雜度為O(n2)，另外還有一種堆排序的方法，將時(shí)間復(fù)雜度降到O(nlogn)

另外一個(gè)類(lèi)似問(wèn)題的介紹

https://www.jianshu.com/p/3948fda91d3d

?

2.海豚數(shù)量

明天做完美團(tuán)筆試再更吧，又要求虐啦/(ㄒoㄒ)/~~

總結(jié)

以上是生活随笔為你收集整理的携程笔试(惨败经历）第一题 leetcode 253的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。