Count meetings in progress at a time, then support editing meeting times

You are given a set of meetings, each with a start time and an end time. Answer how many meetings are in progress at a given moment. In the follow-up, meeting times can be changed after the meetings are added, and you design the class that supports this. ### Clarifying Questions - Is a meeting that ends exactly at time t still in progress at t? Does one that starts exactly at t count? - Are times integers, such as minutes, or arbitrary numbers, and are they bounded? - Roughly how many meetings and how many queries should the solution handle? ### Part 1 — Meetings in progress at a moment Write a function that takes the meetings and a time `t` and returns the number of meetings in progress at `t`. Then make it efficient for the case where the meetings are fixed and many different times are queried. ```hint Precompute once Instead of checking every meeting against t on each query, ask what you could precompute about all the start times and all the end times. ``` #### What This Part Should Cover - Exact boundary semantics and a correct single-query scan - A precomputation that answers each query in logarithmic time, with its complexity - Edge cases: zero-length meetings, duplicate times, and queries outside every meeting ### Part 2 — Meetings whose times can change Meetings can now be added and their start and end times changed after the fact, and counts can still be queried at any time. Design the class: its methods, the data it keeps, and the cost of each operation. ```hint Who pays for a change Decide whether updates or queries should do the work, and pick a structure that keeps sorted times cheap to change. ``` #### Clarifying Questions for this Part - Are updates or queries more frequent? - Can meetings also be deleted, and do callers refer to meetings by an ID? #### What This Part Should Cover - A class API with meeting IDs, validation and updates that cannot leave the data inconsistent - Data structures that keep both updates and queries fast, with their costs - Alternatives chosen by the read/write ratio or by the range of possible times ### What a Strong Answer Covers - Precise in-progress semantics agreed before coding - Correct, tested code for the static version with logarithmic queries - A class design whose structures stay consistent through every update - The complexity of every operation and the trade-offs between designs - Awareness of which libraries are available, such as sorted containers, and a fallback without them ### Follow-up Questions - Return the meetings in progress at t rather than just their count. What structure would you use? - What is the largest number of meetings in progress at once, and when does it first occur? - Meetings become recurring, for example every weekday at the same time. How does counting change? - Many users query and update at the same time. What needs to be synchronized?