本文共 2546 字，大约阅读时间需要 8 分钟。

You are given 'n' appointments. Each appointment contains startime and endtime. You have to return all conflicting appointments efficiently starttime and endtime can range from a few min to few years.

----------------------------------------------------------------------------------------------------------

Three problems:

Insert Interval: O(n). You can use binary search to locate the insert position, However, the complexity of bad case is still O(n).

Merge Interval: O(nlogn)  The complexity of sort.

List conflicting intervals needs O(nlogn) + O(nlogn)   sort + search

Approach:

E5: 4 : 12
E3: 11 : 24
E1: 13 : 15
E2: 18 : 20
E4: 19: 27

Now take the end time of first Event (E5) ie 12 and check in the start time the first event whose start time is greater than 12, in the above example E1 - with start time 13 is the event.
Now we can safely say that all the events less than E1 and greater than E5 are conflicting with E5 - which is E3 in our case.
With the same above logic, E3 is conflicting with E1, E2 and E4.
Time complexity = O(nlogn) for sorting the events on start time + O(nlogn) for searching a all the conflicting events for a given event Ei (1 <= i <= n).
So total time complexity: O(nlogn)

Output of the below code:

Events sorted with start time:
5: 4:12
3: 11:24
1: 13:15
2: 18:20
4: 19:27
Conflicts are: 
1 <> 3 
2 <> 3 4 
3 <> 5 1 2 4 
4 <> 3 2 
5 <> 3 

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;class Interval {public: int s,e,index; Interval(int ss = 0, int ee = 0, int ii = 0):s(ss),e(ee),index(ii){ }};class cmp {public: bool operator()(Interval& x, Interval& y) { if (x.s == y.s) return x.index < y.index; else return x.s < y.s; }};int main() { Interval intervals[5] = {Interval(4,12,5), Interval(11,24,3), Interval(13,15,1), Interval(18,20,2), Interval(19,27,4)}; int i, j, s, e, len = sizeof(intervals) / sizeof(Interval); vector
           
            
             > conflicts(len + 1); vector
             
               vec(intervals, intervals + len); sort(vec.begin(), vec.end(), cmp()); for (i = 0; i < len; ++i) { s = i + 1, e = len - 1; int res = i; while (s <= e) { int mid = (s + e) / 2; if (vec[mid].s > vec[i].e) e = mid - 1; else { res = mid; s = mid + 1; } } for (j = i + 1; j <= res; ++j) { conflicts[intervals[i].index].push_back(intervals[j].index); conflicts[intervals[j].index].push_back(intervals[i].index); } } return 0;}
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://twboi.baihongyu.com/