Katkat
Back

Implement Calendar, Tokenizer, and Meeting Optimizer

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to parse structured meeting request strings into interval objects and then identify the largest subset of non-overlapping meetings that can be scheduled within a fixed workday.

Meeting Scheduler Optimization

You are building a tool to help users manage their calendars. You need to implement a system that parses a list of meeting requests and selects the maximum number of non-overlapping meetings that fit into a single workday.

Part 1: Tokenizer

You are given a list of strings where each string represents a meeting in the format: "[Name]: [StartTime]-[EndTime]". Times are in 24-hour HH:MM format (e.g., "09:00" to "17:00"). Implement a function parse_meetings(meeting_strings) that returns a list of objects or dictionaries with name, start (as minutes from midnight), and end (as minutes from midnight).

Part 2: Optimizer

Given a list of parsed meeting objects, implement a function optimize_schedule(meetings) that returns the maximum number of non-overlapping meetings that can be scheduled. If two meetings have the same end time, prefer the one with the shortest duration (or any arbitrary choice if equal).

Constraints

  • Start and end times are between 00:00 and 23:59.
  • meeting_strings length is between 0 and 1000.
  • Meetings are always within a single calendar day (end > start).

Examples

# Input
meetings = ["A: 09:00-10:00", "B: 09:30-10:30", "C: 10:00-11:00"]

# Expected Output: 2
# Explanation: You can pick (A, C) or (B) is not optimal. (A, C) gives 2 meetings.

Edge Cases

  • Empty input list.
  • Meetings with identical start and end times.
  • Meetings that span the entire day.

Hints

Hint 1

To parse the strings, use a split function on the colon and then split the time range by the hyphen; convert HH:MM to (HH * 60 + MM).

Hint 2

This is a classic 'Interval Scheduling' problem which can be solved greedily by sorting meetings by their end times.

Hint 3

Once sorted by end time, iterate through the meetings and keep track of the end time of the last scheduled meeting to determine if the next one can be added.

Follow-up questions

  • How would you modify the algorithm if each meeting had a 'priority' score, and you wanted to maximize the total priority instead of the total count of meetings?
  • If the scheduler needs to handle recurring weekly meetings, what changes would you make to the data structure?
  • How does your algorithm behave if the meeting list is extremely large (e.g., millions of meetings)? Can you optimize the time complexity beyond O(N log N)?