Interview Scheduler
Imagine this — you landed your dream job at the perfect company. You've worked your way up and are now the lead engineer. It's your turn to start interviewing candidates, and you want to make sure they have an amazing experience.
You want the candidates to meet the entire team, but you realize it's really difficult to find a time that fits all schedules. So, you ask everyone to send you the start and end time of their meetings so you can combine them to determine all the overlapping time blocks. Knowing when the team is free will allow you to effectively schedule the interview process for the candidate.
You receive an array that contains start and end times for each person's meeting times.
The items will be represented as 30-minutes blocks.
For example, 10.5 corresponds to the time 10:30.
If meetings overlap, you want to merge them into a single window that encompasses the earliest start time and latest end time. The solution should contain an array of items where each item is the range for the start and end time of each merged interval of meetings. The input is not guaranteed to be sorted or in any order.
Write a function mergeOverlappingIntervals that returns an array of intervals where the ones with overlapping start and end times are combined to a single interval.
Breakdown
Approach and test strategy
Merge overlapping and touching intervals in start order
Read the approach, boundary cases, and complexity
Sort intervals by start time and compare each with the current merged interval. If they overlap or touch under the course contract, extend the current end to the larger end. Otherwise finish the current interval and start the next. Comparing only neighboring original inputs misses overlaps when intervals arrive unsorted. A contained interval must not shorten an already retained end.
Cases to check
- Test no intervals and one interval.
- Include unsorted, touching, nested, and separated meetings.
- Use half-hour times such as 10.5 consistently with the lesson's representation.
Cost model
Sorting n intervals takes O(n log n), followed by a linear merge. Output may contain n intervals. Auxiliary sorting and copying storage depends on the implementation and input-preservation policy.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
This question has quite a few cases to consider. Try to think through the possible ways these meeting times can appear.
Does your solution combine meetings that touch at the same start and end time? Since there is no time off between them, they should still be combined to the same interval.
If a meeting starts and ends during another meeting, they are part of the same interval. Make sure your code handles this.
If multiple meetings overlap at any point, they should all be combined.
You could solve this by comparing an item to all intervals in O(n2) time, but that's not the best path. The simplest solution is also the one with the best time complexity. You can solve this in O(n log n) time and O(n) space.
Interview Scheduler
You receive an array that contains start and end times for each person's meeting times.
The items will be represented as 30-minutes blocks.
For example, 10.5 corresponds to the time 10:30.
If meetings overlap, you want to merge them into a single window that encompasses the earliest start time and latest end time. The solution should contain an array of items where each item is the range for the start and end time of each merged interval of meetings. The input is not guaranteed to be sorted or in any order.
Write a function mergeOverlappingIntervals that returns an array of intervals where the ones with overlapping start and end times are combined to a single interval.