Interval problems.

I wrote something a long time ago. I hope it helps. Here is the link of my post.

https://leetcode.com/problems/maximum-length-of-pair-chain/discuss/105607/4-Liner-Python-Greedy/113587

1353. Maximum Number of Events That Can Be Attended

For this one, greedy is not working any more.

Build a toy example. This toy example and solution can be found here:

Toy example and solution

We can try to use a naive algorithm below to try to solve the problem.

1. sort the events by event begin time then the earliest begin event will be the first one.
2. Pick up the first day of the first begin event.
3. for the following days, if the begin time is the same as the first day’s begin time, update the begin time to the following day.
4. repeat step 1 to 3 until done.

A visualization of those steps can be found below.

step 1: Left is already sorted. We pick the fist day of fist event as shown in the left image.

step 2: Then for the second event, we update the begin day to make the begin day as the following day as shown in the left image (red cross)

step 3: Sort the rest two events by using updated beginning days. (right image)

step 4: repeat steps 1 to 3 until done.

This Naive algorithm got TLE as the complexity is O(n*n*logn)

//39 / 44 test cases passed.
class Solution {
public:
   int maxEvents(vector<vector<int>>& events) {
       sort(events.begin(), events.end());
       const int n=events.size();
       int begin = INT_MIN, res = 0, i=0;
       while(i<n){
           //after updating the first day of events, we may have the begin day >end day case. Skip this case.
           if(events[i][0]>events[i][1]){i++;continue;}
           /*we have 3 cases here:
           case 1: valid, res++, begin = s+1
            begin
                         s*****************e
           case 2:valid, res++, begin++
                                begin
                         s*****************e
           case 3:invalid, do nothing
                                                    begin     
                         s*****************e         
           */
           if(begin<events[i][0]){begin=events[i][0]+1;res++;}
           else if(events[i][1]>=begin){begin++;res++;}
           i ++;
           // update the flowing events's begining time.
           for(int j=i;j<n;++j){
               if(events[j][0]<begin)events[j][0]=begin;
               else break;            }
           sort(events.begin()+i, events.end());  
       }
       return res;
   }
};

If we improve it to partial_sort, the complexity is kind of O(n k log n), slightly better, still got TLE.

//41 / 44 test cases passed.
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        //for(auto&s:events)cout<<s[0]<<", "<<s[1]<<endl;
        const int n=events.size();
        int begin = INT_MIN, res = 0 ;
        int i=0;
        while(i<n){
            //if(events[i][0]>events[i][1]){i++;continue;}
            if(begin<events[i][0]){begin=events[i][0]+1;res++;}
            else if(events[i][1]>=begin){begin++;res++;}
            i ++;
            int begin_j=i,j=i;
            for(;j<n;++j){
                if(events[j][0]<begin){if(events[j][1]<begin)begin_j++;
                                       else events[j][0]=begin;}
                else break;
            }
            int jj=j;
            for(;jj<n;++jj){if(events[jj][0]!=begin)break;}
            i=begin_j;
            partial_sort(events.begin()+begin_j,events.begin()+jj,events.end());
            
        }
        return res;
    }
};

Actually, we don’t need partical_sort, we can only sort a small part of the problem with the complexity of O(nklogk)

runtime

//264 ms
class Solution {
public:
   int maxEvents(vector<vector<int>>& events) {
       sort(events.begin(), events.end());
       const int n=events.size();
       int begin = INT_MIN, res = 0, i=0;
       while(i<n){
            //after updating the first day of events, we may have the begin day >end day case. Skip this case.
           if(events[i][0]>events[i][1]){i++;continue;}
           /*we have 3 cases here:
           case 1: valid, res++, begin = s+1
            begin
                         s*****************e
           case 2:valid, res++, begin++
                                begin
                         s*****************e
           case 3:invalid, do nothing
                                                    begin     
                         s*****************e         
           */
           if(begin<events[i][0]){begin=events[i][0]+1;res++;}
           else if(events[i][1]>=begin){begin++;res++;}
           i ++;
           // update the flowing events's begining time and recording the ending index j
           int j=i;
           for(;j<n;++j){
               if(events[j][0]<begin)events[j][0]=begin;
               else break; }
           // min(j+1, n) to prevent the out of boundary error.
           sort(events.begin()+i, events.begin()+min(j+1, n));  
       }
       return res;
   }
};

python version is here

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort()
        res, i, begin = 0, 0, -float('inf') 
        for i, (s, e) in enumerate(events):
            if s>e:continue
            """
            we have 3 cases here:
            case 1: valid, res++, begin = s+1
            begin
                         s*****************e
            case 2:valid, res++, begin++
                                begin
                         s*****************e
            case 3:invalid, do nothing
                                                    begin     
                         s*****************e     
            """
            if begin<=s:
                res, begin = res+1, s+1
            elif begin<=e:
                res, begin = res+1, begin+1
            j = i + 1
            while j<len(events):
                if events[j][0]<begin:
                    events[j][0] = begin
                    j += 1    
                else:
                    j += 1
                    break
            j = min(j, len(events))
            # not sure about the partial inplace sorting in python.
            #https://stackoverflow.com/questions/2272819/sort-a-part-of-a-list-in-place
            events[i:j] = sorted(events[i:j])
        return res