viralm's blog

By viralm, history, 3 years ago, In English

We want to schedule interviews for N candidates. We have M intervewers who are available for interviewing candidates.

Each candidate and interviewer provides one or more time intervals during which they are available for interviews all for the same day. Find the maximum number of interviews that can be scheduled assuming each interview is 1 hour long.

The interval times are between 0 hours to 24 hours with granularity of 30 minutes. For example, the time intervals: [0, 3], [22.5, 24] are valid intervals but time intervals like: [0.7, 2] are invalid.

N < 1000
M < 1000

Input: Candidate intervals is a list of lists. The inner list is of the format: [start time, end time, candidate id].

Interviewer intervals is a list of lists. The inner list is of the format: [start time, end time, interviewer id]

Output: Single integer denoting the maximum number of interviews that can be scheduled.

Note: We need to schedule at most one interview per candidate. Exactly one candidate and exactly one interviewer participate in an interview.

  • Vote: I like it
  • +13
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by viralm (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by viralm (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Make 48* interviewer nodes and 48*candidate nodes, now apply maximum bipartite matching.