“This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022”
1353. Maximum number of meetings that can be attended
The title
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.
The sample
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
Answer key
Greed + small top pile
If startDayi <= d <= endDayi is met, you can attend the meeting on any day such as events = [[1,2],[1,2]]; You can go to conference 1 on day 1 and conference 2 on day 2; Don’t wait until after meeting 1 to go to meeting 2. My Chinese is not good. I have been confused here for a long time.
Events = [[1,7],[1,5]]; For the events array, meeting 1 ends on day 7 and meeting 2 ends on day 5.
Therefore, in theory, different meetings should start at the same time, so you should attend the meeting that ends early first, and the meeting that ends later, and then have the opportunity to attend the meeting that ends early.
- You can order events in ascending order by end time.
- Because the end time and end time are the same, those with the earlier start time attend the meeting first
- Events = [[1,5],[2,5],[3,5]];
- You can attend meetings 1, 2, and 3 in total
- For different meeting end times, the meeting before the test is attended first
- Enumeration starts at session 1
- The value day is used to indicate the number of days for which a conference is held. Day +1 is used for each execution whether the conference is attended or not.
- If the start time of a meeting is less than Day, the meeting can be joined. You can add the end time of the meeting to the small top heap first
- The small top heap is empty and enumerates until the last session, the loop ends
Edit the code as follows
code
class Heap {
constructor(compare) {
this.list = [0]
this.compare = typeof compare === 'function' ? compare : this.defaultCompare
}
defaultCompare(a, b) {
return a > b
}
swap(x, y) {
const t = this.list[x]
this.list[x] = this.list[y]
this.list[y] = t
}
isEmpty() {
return this.list.length === 1
}
getSize() {
return this.list.length - 1
}
top() {
return this.list[1]}left(x) {
return 2 * x
}
right(x) {
return 2 * x + 1
}
parent(x) {
return Math.floor(x / 2)}push(val) {
// Add data to the heap end
this.list.push(val)
this.up(this.list.length - 1)}/ / to rise
up(k) {
const { list, parent, compare } = this
while (k > 1 && compare(list[k], list[parent(k)])) {
this.swap(parent(k), k)
k = parent(k)
}
}
pop() {
const { list } = this
if (list.length === 0) return null
this.swap(1, list.length - 1)
const top = list.pop()
this.down(1)
return top
}
down(k) {
const { list, left, right, compare } = this
const size = this.getSize()
while (left(k) <= size) {
let _left = left(k)
if (right(k) <= size && compare(list[right(k)], list[_left])) {
_left = right(k)
}
if (compare(list[k], list[_left])) return
this.swap(k, _left)
k = _left
}
}
}
var maxEvents = function (events) {
events.sort((a, b) = > a[0] - b[0])
/ / small cap pile
const minHeap = new Heap((a, b) = > a < b)
const len = events.length
let index = 0
let result = 0
let end = 1
while(index < len || ! minHeap.isEmpty()) {while (index < len && events[index][0] <= end) {
minHeap.push(events[index][1])
index++
}
while(! minHeap.isEmpty() && minHeap.top() < end) { minHeap.pop() }if(! minHeap.isEmpty()) { minHeap.pop() result +=1
}
end++
}
return result
}
Copy the code
conclusion
I feel that this article is not thorough; Probably because I don’t understand the question clearly enough; Now can understand the first record, tomorrow to understand, gradually improve.