Merge Intervals Interview Question: Interview Schedule |
Interview Question

Interview Scheduler

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

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. This know 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 person's each meeting. 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.

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.

const intervals = [
  { start: 9, end: 10.5 },
  { start: 9.5, end: 10 },
  { start: 10 , end: 11 },
  { start: 10.5 , end: 11.5 },
  { start: 13, end: 14 },
  { start: 13.5, end: 15 },
// [{ start: 9, end: 11.5 }, { start: 13, end: 15 }];

Validate My Answer

  1. This question has quite a few cases to consider. Try to think through the possible ways these meeting times can appear.

  2. 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.

    // Input
    [{ start: 0, end: 5 }, { start: 5, end: 10 }];
    // Combined
    [{ start: 0, end: 10 }];
  3. If a meetings starts and ends during another meeting, they are part of the same interval. Make sure your code handles this.

  4. If multiple meetings overlap at any point, they should all be combined.

    // Input
      { start: 0, end: 3 },
      { start: 2, end: 4 },
      { start: 3, end: 5 },
      { start: 4, end: 6 },
      { start: 3, end: 10 },
    // Combined
    [{ start: 0, end: 10 }];
  5. 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.