366. Find Maximum Meetings in One Room

There is a single meeting room. Given n meetings, each with a start and end time, find the maximum number of meetings that can be held such that no two overlap - one meeting must strictly end before the next starts (they cannot share the boundary instant). Print the count, then the 1-indexed numbers of the chosen meetings, space-separated, in the order they are held.

Input: The first line contains an integer n, the number of meetings. The second line contains n space-separated integers, the start times. The third line contains n space-separated integers, the end times (index-aligned with the start times). Output: Print the count of meetings that can be held, followed by their 1-indexed original positions, space-separated, in the order held.

1 <= n <= 10^5

Remembering each meeting's ORIGINAL index before sorting is essential, since the answer must report meetings by their original numbering, not their position in the sorted order.

Find the maximum number of non-overlapping meetings that can be held in a single room, and which ones. Brute force: Try every possible subset of non-overlapping meetings directly - exponential and impractical for large n, when the same end-time-sort greedy used for activity selection solves this efficiently. Optimised: This is the exact same activity-selection greedy technique, with one small adjustment: the strict inequality (start MUST be greater than, not just at-or-after, the last meeting's end) since this problem explicitly disallows sharing the boundary instant - sorting by end time and greedily selecting remains provably optimal.

Sort meetings by end time, then compute dp[i] = the maximum number of meetings achievable ending with meeting i, by scanning backward over all earlier meetings j to find one whose end time is strictly less than meeting i's start time and taking the best dp[j] + 1. This avoids re-checking full subsets but still costs a linear scan per meeting, giving a quadratic but correct improvement over brute enumeration. Time: O(n^2) Space: O(n)

Sort all meetings by end time. Walk through them in that order and greedily accept a meeting whenever its start time is strictly greater than the end time of the last accepted meeting. An exchange argument shows this is always optimal: among any set of compatible choices, swapping in the meeting that finishes earliest never makes things worse and always leaves the most room for future meetings. Sorting dominates the cost. Time: O(n log n) Space: O(n)

Try every possible subset (or ordering) of meetings and check whether the meetings in it are pairwise non-overlapping, keeping the largest valid subset found. This works because it directly tests the definition of a valid schedule against every possibility, but the number of subsets is exponential (2^n), so it is only feasible for a tiny number of meetings. Time: O(2^n) Space: O(n)

1. Sort meetings by END time, breaking ties by earlier start. 2. Greedily take a meeting only if its start time is STRICTLY greater than the end time of the last meeting taken (meetings can't share the boundary instant here, unlike plain activity selection). 3. Remember each meeting's original 1-indexed position before sorting, so the answer can report which specific meetings were chosen.

Time: O(n log n), dominated by the sort. Space: O(n), for tracking original indices alongside sorted meetings.

meetings sharing a boundary instant (one ending exactly when another starts, which is disallowed), n = 1, and n at its maximum of 10^5 to confirm the sort-and-greedy approach runs efficiently.

Be ready to point out the subtle but important difference from plain activity selection - the STRICT inequality here versus the non-strict one there, driven by this problem's specific 'cannot share the boundary instant' rule.