Mog Scheduling

Process outings in increasing order of their start times. Let $c$ be the number of selected outings that are currently in progress.

If $c<N$, someone is still inside the room, so the next departure does not immediately create a problem. When $c=N$, everybody is outside. Let $x$ be the currently active outing with the earliest finishing time. The owner of $x$ must have taken the key when departing; otherwise that first returning person cannot open the door.

Every maximal period during which the room is empty determines one such compulsory key-carrying outing. These outings must not overlap each other, since the single key cannot be carried by two people simultaneously. Conversely, if they do not overlap, the key can be taken by each designated person in turn, so the schedule is feasible.

Maintain $q$, the return time of the most recently designated key carrier. At a new moment when the room becomes empty, a conflict occurs exactly when $l_x<q$. In this situation, at least one currently active outing must be dropped from the selected set.

It is optimal to discard the currently active outing with the latest ending time. Among simultaneous outings, discarding one that finishes later ensures that a person is available inside the room for at least as long into the future as when an earlier-ending outing is discarded. A standard exchange argument, repeated chronologically, proves the greedy choice. If there is no conflict, set $q\leftarrow r_x$.

Maintain a min-heap and a max-heap ordered by return time, using lazy deletion for expired or discarded outings. Every outing enters and leaves each heap at most once. The time complexity is $O(M\log M)$, and the space complexity is $O(M)$.