“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.