Combinations of meeting rooms usable simultaneously

Problem Given meeting rooms with intervals [start, end], return all combinations of rooms that can be in use simultaneously — every set of rooms whose intervals mutually overlap (share a common time point).

Input / Output

• Input: rooms with intervals, e.g. A:[0,2], B:[1,3], C:[3,5], D:[6,8].
• Output: all usable-together combinations — here AB is invalid? (A and B overlap on [1,2] — clarify!) Expected: AC, AD, BC, BD, CD, ACD, BCD per the source example — so "usable simultaneously" means the rooms do NOT conflict: sets of PAIRWISE NON-overlapping rooms.

Constraints

• Clarify the overlap convention (does end == start conflict? The example says [0,2] and [1,3] conflict, [1,3] and [3,5] don't — half-open intervals). Output is exponential; n is small.

Example

• A:[0,2], B:[1,3], C:[3,5], D:[6,8] → AC, AD, BC, BD, CD, ACD, BCD (size ≥ 2 subsets with no pairwise conflict).

Expected approach

• Build a conflict relation via pairwise interval-overlap checks (a.start < b.end AND b.start < a.end for half-open). Then enumerate subsets with backtracking, extending a set only with rooms conflict-free against all members (independent-set enumeration). Prune by sorting by start. O(2^n) worst case, fine for small n. The real test is pinning down the ambiguous statement with the example before coding.