The maximum number of meetings you can attend [greedy + priority queue]

Preface

Greed is a good type of topic to examine the ability of logical analysis , Like dynamic planning / Monotonic stack / Speed is the same as double pointer . Greed has a class of problems that are often linked to the priority queue , To be precise, it is linked to the priority of the priority queue .

One 、 The maximum number of meetings you can refer to

Two 、 greedy + Priority queue

package everyday.medium;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

//  The maximum number of meetings you can attend .
public class MaxEvents {
    
    /* target: altogether n A meeting , Every meeting lasts 1 Days or more , I can attend a new meeting every day , How many meetings can I attend at most .  Be able to participate   most   Conference , It must be before the end of the meeting   As far as possible   I'll take part in , You have to choose every day endDay  Minimum   The meeting of , Otherwise, if you miss it, you may regret .  Need to take every day as the timeline , Set the meeting schedule of the day endDay Join the priority queue , same day endDay Small open , Kick out after driving , Kick out the meeting at the end of the day . */

    public int maxEvents(int[][] events) {
    
        //  Put the meeting in order by the start date , It is convenient to put the... In order i Days of endDay Put in the priority queue , Otherwise, you need to traverse the array , from O(1) -> O(N).
        Arrays.sort(events, Comparator.comparingInt(o -> o[0]));
        PriorityQueue<Integer> minEndDay = new PriorityQueue<>();

        int curDay = 1;//  The first day 
        int ans = 0;
        for (int i = 0; i < events.length || !minEndDay.isEmpty(); ) {
    
            //  Put what can be opened on and before that day , And those who have not participated in the queue .
            while (i < events.length && curDay == events[i][0]) minEndDay.offer(events[i++][1]);
            //  Take the smallest 
            if (!minEndDay.isEmpty()) {
    
                ans++;
                minEndDay.poll();
            }
            //  Kick the end of the day schedule out of the queue .
            while (!minEndDay.isEmpty() && minEndDay.peek() == curDay) minEndDay.poll();
            //  Open the next day's meeting options .
            ++curDay;
        }
        //  Choose one every day , It is possible to choose a meeting , Maybe the meeting hasn't started yet , Get the last number of meetings .
        return ans;
    }
}

summary

1） Greed is a good topic to examine the ability of logical analysis , More practice .
2） Greed is easily linked to the priority of the priority queue .

reference

[1] LeetCode The maximum number of meetings you can attend