阅后即焚 店面

答案唯一的话可以用下面代码

1.     vector<vector<int>> intervals={{0,3}, {1,3}, {2,4}};
   
2.     sort(intervals.begin(), intervals.end(), [&](const vector<int>& i1, const vector<int>& i2){
   
3.         return i1[0]<i2[0];
   
4.     });
   
5.     vector<int> ret={-1,-1};
   
6.     int max_overlap = 0;
   
7.     auto compare = [](vector<int>& a, vector<int>& b){return a[1]>b[1];};
   
8.     priority_queue<vector<int>, vector<vector<int>>, decltype(compare)> pq(compare);
   
9.     for (const auto& i: intervals) {
   
10.         while(!pq.empty() && pq.top()[1]<i[0])
    
11.             pq.pop();
    
12.         pq.push(i);
    
13.         if (max_overlap<pq.size()) {
    
14.             max_overlap = pq.size();
    
15.             ret = {i[0], pq.top()[1]};
    
16.         }
    
17.     }
    
18.     return ret;

复制代码

dwt585 发表于 2021-4-7 05:17
meeting room套了个马甲

楼主，能仔细说说套了个什么马甲嘛。。。我想了半天都没想出来，求指教啊！

请问有没有最大频率区间为多个的情况？ 要全输出吗？已加米

noi10 发表于 2021-04-07 21:22:43
请问有没有最大频率区间为多个的情况？ 要全输出吗？已加米

对，follow up 输出 最大的range

楼主竟然狗屎运过了

kevinguo09 发表于 2021-4-9 06:37
楼主竟然狗屎运过了

楼主你又不匿名了

Hi 我想了一个solution，不用pq 时间是linear的， 麻烦大家帮忙看一下对不对 ～ 谢谢！

[/i]

1. public int[] findInterval(int[][] arr){
   
2.         int maxEnd = 0;
   
3.         for (int[] a: arr){
   
4.             maxEnd = Math.max(a[1], maxEnd);
   
5.         }
   
6.         // use this 2 dimension array to present how many times a time serves as the start of an interval, and the end of an interval
   
7.         // for example store[4] = {3, 0} means 4 is start point of 3 interval and end point of 0 interval in the example
   
8.         int[][] store = new int[maxEnd][2];
   
9.         for (int[] a: arr){
   
10.             store[a[0]][0] ++;
    
11.             store[a[1]][1] ++;
    
12.         }
    
13.         
    
14.         int maxFrequency = 0, start = 0, end =0;
    
15.         boolean toFindEnd = false; // Indicate if we should start to find the end
    
16.         for(int i=0; i<maxEnd; i++) {
    
17.             if(store[i][0]> maxFrequency) { // i must be the answer for the start
    
18.                 maxFrequency = store[i][0];
    
19.                 start = i;
    
20.                 toFindEnd = true; // Enable to start search for the endpoint, and only update once.
    
21.             } else {
    
22.                 if(toFindEnd && store[i][1] > 0 && i>start)
    
23.                     end = i;
    
24.                     toFindEnd = false;
    
25.             }
    
26.         }
    
27.         return new int[] {start, end};
    
28. }

复制代码

[i]

楼主几年经验

请问这个这个频率最大区间不一定是给的interval的区间对吧， 比如你的例子里，如果把input的[4,5]换成[0,5], 最后的结果还是[4,5] 对么？

听起来 和这道题很相像https://www.geeksforgeeks.org/fi ... -intervals-overlap/