“This is the 23rd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

Events [I] = [startDayi, endDayi], indicating that meeting I starts at startDayi and ends at endDayi.

You can attend meeting I on any day d that satisfies startDayi <= d <= endDayi. Note that you can only attend one meeting per day.

Please return the maximum number of meetings you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]] output: 3 explanation: you can attend all three meetings. One way to schedule a meeting is as shown above. Attend the first meeting on day 1. Go to the second meeting on day 2. Day 3: Attend the third meeting.Copy the code

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]] output: 4Copy the code

Tip:

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

Their thinking

First of all, how can we attend as many meetings as possible? The answer is that if two meetings start at the same time, the earlier one should be preferred, because we have more days available for the later one. Similarly, if two meetings end at the same time, the earlier days should be used to cancel the earlier meetings. Therefore, you can sort the meeting list by the end time from morning to evening. If the end time is the same, the meeting with the earlier start time is ranked first. Why not sort by ascending start time first, and then by ascending end time if the start time is the same? This is because some meetings start earlier but end later. If we deal with them first, some meetings that start later and end earlier will not have time to attend. Therefore, we cannot attend as many meetings as possible. Next, we traverse the sorted meetings and judge whether each day within the meeting time is free from morning to night. We find the first free day. If the day is within the meeting time, the current meeting can be joined, record the number of available meetings, and mark the current day as occupied. This approach is fine, but because finding the number of days available for meetings is inefficient, you can exceed the time limit. So we need to think about how can we speed up or quickly find the first free day after the current meeting start time? Actually such a similar Yu Liantong relationship problems, if the current number is already in use, we mark the next free number is the next day, while this tag should be give to the current number of days before been occupied the number of days in a row, so can be abstracted into a connected, connected relationship behind the number of days recorded together in the first free days. When it comes to maintaining this connectivity, we can use and look up sets. If you still don’t know about parallel collection, you can go to my article “parallel collection”. We won’t go into details here.

Therefore, it is necessary to solve the problem as follows: Descending order according to the end of time for meeting, if the end of the time the same, then the start time ascending order Create and look set to maintain the current number of days behind the first free days Traverse the list sorted meeting, get behind the meeting start time of the first free days, if the number of days not later than the end of time, the current meeting can participate in, record the meeting number, The first idle day after the current idle days are updated is the next day. Because the current data is being maintained and the set is being queried, the next idle time corresponding to the current idle day will be updated to the next idle day.

Code implementation

Class UnionFind {constructor(n){this.list = Array(n) for(let I = 0; i<n; i++){ this.list[i] = i; List [x]= this.list[x]= this.list[x] return this.list[x]= this.list[x] return this.list[x]} // Merge (a,b){const rootA = this.find(a), RootB = this.find(b) this.list[rootA] = rootB}} var maxEvents = function(events) {rootB = this.find(b) this.list[rootA] = rootB}} var maxEvents = function(events) { Sort ((a,b) => a[1]===b[1]? A [0]-b[0]:a[1]-b[1]) Length = latest number of days +1 const uf = new UnionFind(events[events.length-1][1]+1) // let res = 0 // traverses the sorted conference list for(let I = 0; i<events.length; Const [a,b] = events[I], const [a,b] = events[I], const [a,b] = events[I], day = uf. If (day<=b) uf. Merge (day,day+1),res++} return res};Copy the code

At this point we have leetcode-1353- the maximum number of meetings that can be attended

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻