Practice/Google/Car Rental Optimization

Car Rental Optimization

CodingMust

Problem

You are building a conference room scheduling system. Given a list of meeting requests, each specified by a start time, end time, and unique meeting ID, assign each meeting to a conference room using the minimum number of rooms possible.

A meeting occupies a room from its start time up to (but not including) its end time. Two meetings can use the same room if one ends exactly when the other starts.

Return a dictionary/object mapping each meeting ID to its assigned room number. Room numbers should start from 0 and be assigned sequentially as needed.

Requirements

1. Minimize the total number of conference rooms used
2. Each meeting must be assigned to exactly one room
3. No two meetings in the same room can overlap in time
4. Room numbers must start from 0 and increment sequentially (0, 1, 2, ...)
5. Return a mapping from meeting ID to room number

Constraints

• 1 ≤ number of meetings ≤ 10,000
• 0 ≤ start time < end time ≤ 1,000,000
• Meeting IDs are unique positive integers
• Expected time complexity: O(n log n) where n is the number of meetings
• Expected space complexity: O(n)

Examples

Example 1:

` Input: meetings = [[0, 30, 1], [15, 45, 2], [50, 70, 3]] Output: {1: 0, 2: 1, 3: 0} Explanation:

• Meeting 1 (0-30) is assigned to room 0
• Meeting 2 (15-45) overlaps with meeting 1, so it needs room 1
• Meeting 3 (50-70) starts after meeting 1 ends, so it can reuse room 0 Total rooms used: 2 `

Example 2:

` Input: meetings = [[0, 10, 101], [10, 20, 102], [20, 30, 103]] Output: {101: 0, 102: 0, 103: 0} Explanation:

• All meetings are back-to-back with no overlap
• They can all use the same room (room 0) Total rooms used: 1 `

Example 3:

` Input: meetings = [[0, 100, 1], [10, 50, 2], [20, 60, 3], [30, 40, 4]] Output: {1: 0, 2: 1, 3: 2, 4: 3} Explanation:

• At time 30, all four meetings are active simultaneously
• This requires 4 separate rooms Total rooms used: 4 `