Maximum Meetings Attendance

Given a list of meetings where each meeting is represented as [start, end], determine the largest number of meetings you can attend if you can only be in one meeting per day and you may pick any day within the inclusive interval [start, end] to attend that meeting.

Intuition

The key observation is that we want to finish meetings as early as possible to leave room for later ones. Therefore we sort the meetings by their end day. For each meeting we then greedily pick the earliest still-free day inside its interval.

Algorithm

1. Sort the meetings by ascending end day. If two meetings end on the same day, the one that starts earlier is preferred.
2. Sweep the timeline from day 1 to the largest end day.
   • Maintain a min-heap of currently open meetings (those whose start ≤ currentDay ≤ end).
   • At each day, pop the meeting with the smallest end day from the heap and occupy this day.
   • Push into the heap every meeting whose start == currentDay.
3. The number of occupied days is the answer.

Complexity

• Sorting: O(n log n)
• Heap operations: each meeting is inserted and extracted once ⇒ O(n log n)
• Overall: O(n log n) time, O(n) space.

Reference implemantation (Python)

import heapq

def max_meetings(events):
    events.sort(key=lambda x: (x[1], x[0]))
    heap = []
    res = 0
    cur = 1
    i = 0
    n = len(events)
    while heap or i < n:
        while i < n and events[i][0] <= cur:
            heapq.heappush(heap, events[i][1])
            i += 1
        while heap and heap[0] < cur:
            heapq.heappop(heap)
        if heap:
            heapq.heappop(heap)
            res += 1
        cur += 1
    return res

Reconstructing Target Array from All-Ones Array

Start with an array A filled with 1s. In each move you may pick any index i, compute the current sum S of the whole array, and set A[i] = S. Determine whether a given target array can be produced by any sequence of such moves.

Reverse Thinking

Instead of building the array forward, undo the last operation: the largest element in the current array must have been the one that was just updated. Its previous value was max - (sum - max). Repeat this process until either every element becomes 1 (successs) or an impossible state is reached.

Algorithm

1. Use a max-heap to repeatedly extract the current maximum.
2. Compute the previous value prev = max - (sum - max).
3. If prev ≤ 0 or the heap becomes empty while some element is still greater than 1, return False.
4. Otherwise push prev back into the heap and continue.

Complexity

• Each element is processed log(target[i]) times in the worst case.
• Each heap operation is O(log n).
• Overall: O(n log n log(max(target))) time, O(n) space.

Reference implementation (Python)

import heapq

def can_construct(target):
    total = sum(target)
    max_heap = [-x for x in target]
    heapq.heapify(max_heap)
    
    while True:
        cur = -max_heap[0]
        if cur == 1:
            return True
        rest = total - cur
        if rest <= 0:
            return False
        prev = cur - rest
        if prev < 1:
            return False
        heapq.heapreplace(max_heap, -prev)
        total = rest + prev