Design a Calendar Scheduling System (Set/Map)

To design a conflict detection system, I would first clarify if meetings are open intervals. Assuming we need O(log N) performance for large calendars, a balanced Binary Search Tree or an Interval Tree is superior to a simple sorted list. In a standard BST approach, we store intervals ordered by start time. When inserting a new event, we search for the node with the largest start time less than or equal to our new start time. We then check if that node's end time exceeds our new start time. If it does, a conflict exists. For the Interval Tree approach, each node stores the maximum end time in its subtree, allowing us to prune branches quickly during the search. This ensures we only visit relevant nodes. For example, if a user tries to schedule a meeting from 2 PM to 3 PM, the system checks if any existing meeting overlaps. A sorted list requires scanning all entries, taking O(N), while the tree reduces this to O(log N). Given Salesforce's focus on handling millions of records, the tree-based approach offers better scalability. I would also handle edge cases like back-to-back meetings depending on business rules, ensuring the system remains robust under load.