Filter Hotels by Continuous Availability and Compute Prices

Problem Implementation-heavy: given hotels with per-date availability (and nightly prices), a check-in and check-out date, return the hotels available for EVERY night in the range, with their total stay price.

Input / Output

• Input: hotels[] each with available dates → price; checkIn, checkOut.
• Output: eligible hotels with computed total (or per-night) price.

Constraints

• Continuous coverage required — availability on [checkIn, checkOut) means every night, checkout day exclusive (state this convention). Many hotels × long ranges → per-query linear scans of date lists should be improved.

Example

• Hotel A available Jan 1–5, query Jan 2–4 → eligible (nights of 2nd and 3rd); query Jan 4–7 → not eligible (missing 5th/6th nights).

Expected approach

• Data structure first: per hotel, a date → price hash map (O(nights) check per hotel), or sorted disjoint availability intervals (binary search: the range must fall inside one interval — O(log k)); a bitset over a bounded calendar window makes the contiguity check an AND. Then sum nightly prices for eligible hotels. Discuss trade-offs (memory vs query speed), pre-indexing hotels by date for the inverted query ("which hotels on date d" → intersect), and complexity for H hotels × N nights. Clean decomposition (parse → eligibility → pricing) is a large part of the grade.