## Saturday, July 30, 2016

### integral time stamps

interval [startTime, stoptime)   ----integral  time stamps

startTime <= t< stopTime 代表这个数在区间里面出现过。

example：  [1,3),  [2, 7),   [4,  8),   [5, 9)
5和6各出现了三次， 所以答案返回5，6。

http://blog.5ibc.net/p/52775.html
```     vector<int> findTimeStamp(vector<pair<int,int>>& intervals) {
vector<int> res;
int len=intervals.size();
if(len==0) return res;
vector<int> start(len);
vector<int> end(len);
for(pair<int,int> interval:intervals) {
start.push_back(interval.first);
end.push_back(interval.second-1);
}
sort(start.begin(),start.end());
sort(end.begin(),end.end());
int available=0;
int sIndex=1,eIndex=0;
int ss=start[0],ee=end[0];
while(sIndex<len&&eIndex<len) {
while(start[index]>=end[eIndex]) {
available++;
eIndex++;
}
if(start[sIndex]<end[eIndex]) {
if(available<=0) {
ss=start[sIndex];  //记录起点和终点
ee=end[eIndex];
}
else {
available--;
}
}
sIndex++;
}
for(int i=ss;i<=ee;i++) {
res.push_back(i);
}
return res;
} ```

 这题就是LC上面的meeting rooms换了马甲。meeting rooms求最少需要多少个room，也就是某个时刻有几个并行的会议，这个题目求时刻有最大的并行interval数量，差不多，按照start time排一遍，再用一个heap放结束时间就可以了
1. def integraltimestamps2(intervals):.鏈枃鍘熷垱鑷�1point3acres璁哄潧
2.     intvs = sorted(intervals, key = lambda x : x[0])
3.     edges = sorted([intv[0] for intv in intervals]+[intv[1] for intv in intervals])
4.     results = []. visit 1point3acres.com for more.
5.     moccurs = 0
6.     ongoing = []
7.     intvid = 0
8.     for e in edges:. 鍥磋鎴戜滑@1point 3 acres
9.         if results and len(ongoing) == moccurs:
10.             results += range(results[-1]+1,e)
11.         while ongoing and e >= ongoing[0]:
12.             heapq.heappop(ongoing). 1point 3acres 璁哄潧
13.         while intvid < len(intvs) and e >= intvs[intvid][0]:
14.             heapq.heappush(ongoing, intvs[intvid][1]). from: 1point3acres.com/bbs
15.             intvid += 1
16.         if len(ongoing) > moccurs:
17.             moccurs = len(ongoing)
18.             results = [e]
19.         elif len(ongoing) == moccurs:.鏈枃鍘熷垱鑷�1point3acres璁哄潧
20.             results.append(e)
21.     return results