Android程序員會(huì)遇到的算法(part 6 優(yōu)先級(jí)隊(duì)列PriorityQueue)
又是隔了四個(gè)多月才更新，從十月底來(lái)到美國(guó)開(kāi)始上班，中間雜七雜八的事情很多，加上感恩節(jié)圣誕節(jié)放假出去玩了幾趟，一直拖到現(xiàn)在。
這一次我想講一個(gè)比較經(jīng)典的Java里面的數(shù)據(jù)結(jié)構(gòu)。PriorityQueue，優(yōu)先級(jí)隊(duì)列的一些對(duì)應(yīng)的算法題。
優(yōu)先級(jí)隊(duì)列聽(tīng)起來(lái)很唬，其實(shí)就是一個(gè)幫助大家排序的數(shù)據(jù)結(jié)構(gòu)而已，只不過(guò)它把插入->push,和獲取隊(duì)列頭結(jié)點(diǎn)->poll()給封裝起來(lái)了而已。
在很多面試的算法輪中，直接要求面試者去寫(xiě)排序算法的已經(jīng)很少很少了，第一是排序算法其實(shí)寫(xiě)起來(lái)其實(shí)不簡(jiǎn)單。。。。。 :joy::joy::joy::joy::joy::joy: ，第二是現(xiàn)在排序算法已經(jīng)很成熟，問(wèn)也問(wèn)不出什么門(mén)道來(lái)。所以很多情況下面試官會(huì)更加傾向于問(wèn)面試者對(duì)于排序場(chǎng)景下，一些子場(chǎng)景的算法。在Java里面，PriorityQueue已經(jīng)提供了大部分我們需要的api，所以接下里我們就看看有哪些經(jīng)典的優(yōu)先級(jí)隊(duì)列的算法題。
1. 會(huì)議室問(wèn)題
會(huì)議室問(wèn)題可以說(shuō)是排序/優(yōu)先級(jí)隊(duì)列應(yīng)用的最具代表性的題目之一了。問(wèn)題很簡(jiǎn)單，就是在給定一組會(huì)議的數(shù)據(jù)之后，判斷某一個(gè)人能否完整的參加完所有會(huì)議，或者換個(gè)角度，會(huì)議安排者最少需要安排多少會(huì)議室，才能讓所有會(huì)議都照常舉辦(沒(méi)有會(huì)議室沖突)。
假設(shè)給定一個(gè)數(shù)據(jù)結(jié)構(gòu)，
public class Interval {
/**
會(huì)議開(kāi)始時(shí)間
**/
int start;
/**
會(huì)議結(jié)束時(shí)間
**/
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
}
我們要實(shí)現(xiàn)一個(gè)boolean返回值的方法
public boolean canAttendMeetings(Interval[] intervals)
在給定一個(gè)List of Interval的情況下，判斷一個(gè)人能不能完整的參于所有l(wèi)ist里面的會(huì)議。比如:
兩個(gè)箭頭線段代表一個(gè)會(huì)議的跨越時(shí)長(zhǎng)，在上圖里面，兩個(gè)會(huì)議直接沒(méi)有重疊，正如圖中的紅線所示，就算紅線一直平行的從左往右移動(dòng)，也不會(huì)橫截超過(guò)一個(gè)會(huì)議的箭頭線段。所以在上圖的情況，一個(gè)人是可以參與所有會(huì)議的。
但是下圖所示：
這些情況下，一個(gè)人就不能參與所有的會(huì)議了，很明顯紅線可以同時(shí)穿過(guò)兩個(gè)會(huì)議的箭頭線段。
那么判斷的方法是什么呢?
以正常的思維去想，肯定會(huì)覺(jué)得，我們是不是要去寫(xiě)一個(gè)循環(huán)，按照時(shí)間沒(méi)走一秒就去循環(huán)判斷所有的會(huì)議是不是在這個(gè)時(shí)間上有會(huì)議，如果超過(guò)一個(gè)就返回false?
這樣做是肯定不行的，因?yàn)槟悴淮_定時(shí)間的細(xì)粒度，是秒呢?還是毫秒？還是分鐘？在不確定這個(gè)的情況下，我們是沒(méi)法寫(xiě)for 循環(huán)的。
那么我們可以換一種思路，既然不能for 循環(huán)，那能不能把每次某個(gè)會(huì)議開(kāi)始或者結(jié)束當(dāng)成一個(gè)事件Event，每種事件Event可以分兩種類(lèi)型，一種是開(kāi)始start，一種是結(jié)束end，我們只需要對(duì)當(dāng)前所有的全部事件進(jìn)行排序之后分析，而不需要對(duì)時(shí)間本身進(jìn)行循環(huán)。
比如:
按照時(shí)間線來(lái)排序的話，我們會(huì)先后有三個(gè)會(huì)議，這三個(gè)會(huì)議的起始start以此排列，從此圖的示例我們可以輕松的看出，同時(shí)會(huì)有三個(gè)會(huì)議進(jìn)行。但是理由呢？理由是因?yàn)槟憧吹搅司€段的重疊么？真正的理由是當(dāng)三個(gè)start事件進(jìn)入之后，我們的第一個(gè)end事件才進(jìn)入。
所以，再對(duì)所有事件排序好之后，每當(dāng)我們有一個(gè)start事件，會(huì)議室數(shù)量就需要+1，每當(dāng)我們有一個(gè)end事件的時(shí)候，會(huì)議室數(shù)量就-1.因?yàn)閑nd代表一個(gè)會(huì)議結(jié)束，因此所需要的會(huì)議室數(shù)量可以減少。
有了這個(gè)前提之后，我們就可以寫(xiě)代碼了。
先定義一個(gè)事件:
public class TimeEvent {
/**start類(lèi)型
**/
public static final int start = 0;
/**end類(lèi)型
**/
public static final int end = 1;
/**該事件發(fā)生的時(shí)間
**/
public int time;
/**該事件的類(lèi)型，是開(kāi)始還是結(jié)束
**/
public int type;
public TimeEvent(int type, int time) {
this.type = type;
this.time = time;
}
}
public boolean canAttendMeetings(Interval[] intervals) {
if (intervals.length == 0) {
return true;
} else {
/**
**定義一個(gè)優(yōu)先級(jí)隊(duì)列，事件按照時(shí)間從小到大排列
**/
PriorityQueue<TimeEvent> priorityQueue = new PriorityQueue<>(new Comparator<TimeEvent>() {
@Override
public int compare(TimeEvent o1, TimeEvent o2) {
// TODO Auto-generated method stub
if (o1.time == o2.time) {
/**
**這里兩個(gè)if暫時(shí)可能很難理解，我在下面會(huì)解釋
**/
if (o1.type == TimeEvent.start && o2.type == TimeEvent.end) {
return 1;
}
if (o2.type == TimeEvent.start && o1.type == TimeEvent.end) {
return -1;
}
}
return o1.time - o2.time;
}
});
for (int i = 0; i < intervals.length; i++) {
/**
**把事件的起始和結(jié)束事件創(chuàng)建出來(lái)并且放入優(yōu)先級(jí)隊(duì)列
**/
priorityQueue.add(new TimeEvent(TimeEvent.start, intervals[i].start));
priorityQueue.add(new TimeEvent(TimeEvent.end, intervals[i].end));
}
int max = 0;
int current = 0;
while (!priorityQueue.isEmpty()) {
TimeEvent event = priorityQueue.poll();
if (event.type == TimeEvent.start) {
/**如果是開(kāi)始事件，會(huì)議室數(shù)量+1，只要會(huì)議室數(shù)量大于等于2，返回false
/
current = current + 1;
if (current >= 2) {
return false;
}
} else {
/**如果是開(kāi)始事件，會(huì)議室數(shù)量-1.代表到這個(gè)時(shí)間為止，一個(gè)會(huì)議結(jié)束了。雖然我們
**并不在乎是哪一個(gè)會(huì)議結(jié)束了。
**/
current = current - 1;
}
}
return true;
}
}
上面代碼里面注釋的這一段:
if (o1.type == TimeEvent.start && o2.type == TimeEvent.end) {
return 1;
}
if (o2.type == TimeEvent.start && o1.type == TimeEvent.end) {
return -1;
}
其實(shí)是處理這樣的一種邊界情況:
當(dāng)后一個(gè)事件的start和前一個(gè)事件的end是同一時(shí)間的時(shí)候，這種情況算是需要兩個(gè)會(huì)議室還是一個(gè)？
答案是看情況。。。。。
假如題目要求這種情況只需要一個(gè)會(huì)議室，那么，假如兩個(gè)TimeEvent，分別是start與end，time也相同，我們必須優(yōu)先處理end，因?yàn)橄忍幚韊nd，我們的會(huì)議室數(shù)量就會(huì)先做-1.
按照?qǐng)D中的例子會(huì)議室數(shù)量會(huì):1,0,1,0這樣的變化。
假如題目要求這種情況只需要兩個(gè)個(gè)會(huì)議室，那么，假如兩個(gè)TimeEvent，分別是start與end，time也相同，我們必須優(yōu)先處理start，因?yàn)橄忍幚韘tart，我們的會(huì)議室數(shù)量就會(huì)先做+1.
按照?qǐng)D中的例子會(huì)議室數(shù)量會(huì):1,2,1,0這樣的變化。
兩種情況會(huì)議室的峰值不一樣。所以再回到上段代碼，相信你可以理解代碼中的if對(duì)應(yīng)哪種情況了吧？
2. 合并線段的問(wèn)題
假設(shè)給定一組線段，要求把重疊在一起的線段整合成新的線段返回，比如：
一種情況
第二種情況
第三種情況，沒(méi)變化：
這里的解題思路和上面一樣，先把每個(gè)線段安裝開(kāi)始時(shí)間排序，不同的是，每次在處理當(dāng)前線段的時(shí)候，需要和上一個(gè)線段做對(duì)比，看看有沒(méi)有重疊，如果重疊了，則需要?jiǎng)h除上一個(gè)線段并且生成新的線段。
這里，一個(gè)棧Stack可以完美的處理！
步驟如下，
1.線段在優(yōu)先級(jí)隊(duì)列里面排好序
2.每次提取隊(duì)列第一個(gè)線段
3.與stack中的棧頂線段作對(duì)比，
4.如果有重疊，pop棧頂線段，生成新的線段放入棧頂，重復(fù)第一步
我們每次只需要處理?xiàng)ｍ斁€段的原因是，如果棧頂線段和棧頂線段之前的棧內(nèi)線段有沖突的話，我們?cè)谥暗囊徊揭呀?jīng)處理好了，所以當(dāng)前隊(duì)列的第一個(gè)線段，是絕對(duì)不可能和非棧頂線段有重疊的。
代碼如下：
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
/**
**用優(yōu)先級(jí)隊(duì)列把所有線段排好序，按照起始時(shí)間
**/
PriorityQueue<Interval> priorityQueue = new PriorityQueue<Interval>(new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
};
});
for (int i = 0; i < intervals.size(); i++) {
priorityQueue.add(intervals.get(i));
}
priorityQueue.add(newInterval);
/**
**用棧保存處理過(guò)的線段
**/
Stack<Interval> stack = new Stack<>();
stack.push(priorityQueue.remove());
/**
**while循環(huán)處理線段
**/
while (!stack.isEmpty() && !priorityQueue.isEmpty()) {
Interval inItem = priorityQueue.remove();
Interval originalItem = stack.pop();
/**
**當(dāng)線段不完全重疊的時(shí)候，取兩者的最小開(kāi)始時(shí)間和最大結(jié)束時(shí)間，生成新的線段
**/
if (inItem.start <= originalItem.end && inItem.end > originalItem.end) {
stack.push(new Interval(originalItem.start, inItem.end));
/**
**當(dāng)線段完全重疊的時(shí)候，取兩者的中覆蓋面最大的那一線段
**/
} else if (inItem.start <= originalItem.end && originalItem.end >= inItem.end) {
stack.push(originalItem);
}
/**
**當(dāng)線段沒(méi)有重疊的時(shí)候，兩者一起入棧
**/
else {
stack.push(originalItem);
stack.push(inItem);
}
}
/**
**因?yàn)閟tack的輸出是倒著來(lái)的，所以翻轉(zhuǎn)一次。。。
**/
Stack<Interval> stack2 = new Stack<>();
while (!stack.isEmpty()) {
stack2.push(stack.pop());
}
ArrayList<Interval> arrayList = new ArrayList<>();
while (!stack2.isEmpty()) {
arrayList.add(stack2.pop());
}
return arrayList;
}
PS:其實(shí)筆者在寫(xiě)完之后才發(fā)現(xiàn)其實(shí)用一個(gè)LinkedList來(lái)代替代碼中的stack更好一些。。。?？梢圆恍枰D(zhuǎn)一次。讀者可以自行摸索。。。
2. 城市天際線問(wèn)題
最后一個(gè)問(wèn)題留給讀者們自己去思考，城市天際線問(wèn)題：
在給出若干組城市建筑的坐標(biāo)和高度之后，返回最后應(yīng)該畫(huà)出來(lái)的天際線的樣子，這題也是需要對(duì)數(shù)據(jù)進(jìn)行排序，按照事件來(lái)處理的題目。屬于稍微復(fù)雜一點(diǎn)的問(wèn)題，但是原則還是一樣，需要用到優(yōu)先級(jí)隊(duì)列來(lái)處理。
