Problem

You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

You can attend an event i at any day d where startTimei <= d <= endTimei. You can only attend one event at any time d.

Return the maximum number of events you can attend.

Examples

Example 1:

1
2
3
4
5
6
7

Input: events =[[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

1
2

Input: events=[[1,2],[2,3],[3,4],[1,2]]
Output: 4

Constraints:

  • 1 <= events.length <= 105
  • events[i].length == 2
  • 1 <= startDayi <= endDayi <= 105

Solution

Method 1 - Using Segment Tree

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

class Solution {
    
    int[] tree;
        
    public int maxEvents(int[][] events) {
        
        Arrays.sort(events , (a, b) -> Integer.compare(a[1], b[1]));
        
        int start = events[0][0];
        int end = start ;
        for(int i =0 ; i< events.length ; i++){
            if(events[i][1] > end){
                end = events[i][1];
            }if(events[i][0] <start){
                start = events[i][0];
            }
        }
		
        createST(start,end);
        buildST(0 , start, end);

        int count = 0;        
        for(int[] range : events){
          int day = query(0 , range[0], range[1], start , end);
          
          if(day != Integer.MAX_VALUE && day >= range[0] && day <= range[1] ){
              update(0, day , start, end );
              count++;
          }
      }
        return count;
        
    }
    
    public int update(int idx , int pos , int start , int end ){
        //the day has been already used for other event . Making it unavailable
        if(start == end ){
            return tree[idx] = Integer.MAX_VALUE;
        }else{
            int mid = (start + end)/2;
            //update the sub tree where pos is located 
             if(pos <= mid){
                tree[idx]= Math.min(tree[2*idx+2],update(2*idx+1 ,pos,start,mid));
             }else{
                tree[idx] = Math.min(tree[2*idx+1],update(2*idx+2 ,pos,mid+1,end));
             }
        }
        
        return tree[idx];
    }
    
    public int query(int idx , int qStart , int qEnd, int start , int end){
        
        //full overlap
        if(qStart <= start && qEnd >= end) {
            return tree[idx];
        }
        int mid = (start+ end)/2;
        
        // no overlap
        if(qStart > end || qEnd < start){
            return Integer.MAX_VALUE;
        }
        
        //partial overlap
        int qOut = Math.min(query(2*idx+1 ,qStart,qEnd, start, mid), query(2*idx+2,qStart,qEnd , mid+1 , end));
        
        return qOut;
    }
    
    public int buildST(int idx , int low , int hi){
        if(low == hi){
            
            tree[idx] = low;
            
        }else if(low < hi){
        
        int mid = (low + hi)/2;
        tree[idx] = Math.min(buildST(2*idx+1,low,mid), buildST(2*idx+2,mid+1,hi));
            
        }
        return tree[idx];
    }
    
    
    
    public void createST(int start , int end ){
        int len = end-start+1;
        int height = (int)Math.ceil(Math.log(len)/Math.log(2));
        int n =(int)Math.pow(2,height+1)-1;
        tree = new int[n];
    }
}