LeetCode-1353.最大参加可能な会議数貪欲+優先キュー

ここではテーマの説明です:LeetCode-1353.最大参加可能な会議数
欲張り+優先キュー解法
私たちは貪欲な原則を使用します.ある日複数の会議に参加できるとき、私たちは終了時間が一番早く参加することを選択します.
私たちは優先キューを使用して当日参加できる会議を格納し、優先度は会議の終了時間によって決定され、O(1)の時間オーバーヘッドの中で終了時間の最も早い会議を見つけてキューを出させ、会議数+1に参加することを保証する.
では、ある日、どの会議に参加できるかをどのように確定しますか?私たちは事前に会議を格納する配列を開始時間昇順に並べ、ある日、当日を開始時間とするすべての会議を優先キューに入れ、優先キューを挿入する時間の複雑さはO(logn)である.そして、チームヘッドからのクリア終了時間が当日より早いが、まだ参加されていない会議.
優先キューがどのように実現されるかについては、java.util.PriorityQueueを使用しています.皆さんも自分でスタックで優先キューを実現してみてください.
JAva問題解コード:

class Solution {
    public int maxEvents(int[][] events) {
        if(events.length<=1)
        {
            return events.length;
        }
        Event[] eventArr=new Event[events.length];
        int eariest=events[0][0],latest=events[0][1];
        for(int i=0;i<events.length;i++)
        {
            eventArr[i]=new Event(events[i][0],events[i][1]);
            eariest=Math.min(eariest,events[i][0]);
            latest=Math.max(latest,events[i][1]);
        }
        Arrays.sort(eventArr,new EventComparator()); //         
        PriorityQueue<Event> canJoin=new PriorityQueue<>(); //              ，           ，      ，     
        int numJoin=0; //        
        int index=0;
        for(int day=eariest;day<=latest;day++)
        {
            for(;index<eventArr.length;index++) //              
            {
                if(eventArr[index].start<=day)
                {
                    canJoin.offer(eventArr[index]);
                }
                else
                {
                    break;
                }
            }
            while(!canJoin.isEmpty()) //               
            {
                if(canJoin.peek().end<day)
                {
                    canJoin.remove();
                }
                else
                {
                    break;
                }
            }
            if(!canJoin.isEmpty()) //                   ，     +1
            {
                canJoin.remove();
                numJoin++;
            }
        }
        return numJoin;
    }
}
class Event implements java.lang.Comparable<Event> //     
{
    int start;
    int end;
    Event(int start,int end)
    {
        this.start=start;
        this.end=end;
    }
    @Override
    public int compareTo(Event e) //           
    {
        return this.end-e.end;
    }
}
class EventComparator implements java.util.Comparator<Event> //    Event   
{
    @Override
    public int compare(Event e1,Event e2) //           
    {
        return e1.start-e2.start;
    }
}

時間の複雑さ:優先キューにすべての要素O(nlogn)をソートして挿入し、すべての要素優先キューはキューO(n)をリストするので、O(nlogn)
空間複雑度:O(n)