Frontend School

Resource Availability with Time Zone Adjustments

DSA
hard

Resource Availability with Time Zone Adjustments

Hard
Intervals
Sorting
time zones
Data Structures

Overview

Organizations often manage shared resources like meeting rooms, development environments, or specialized equipment across distributed teams operating in different time zones. Efficiently scheduling these resources requires accurately converting local times to a common reference and detecting conflicts. This problem challenges you to implement a core component for such a scheduling system, determining the feasibility of new resource requests against existing bookings, while correctly accounting for time zone differences.

What you need to do / Task

You are tasked with implementing a function that evaluates a list of resource requests against a set of existing bookings. For each request, you must determine if it can be accommodated without overlapping any existing booking. All times are provided in local time, along with their respective time zone offsets from UTC, which must be correctly applied before checking for overlaps.

Specifically, your function should:

  1. Convert all given localStartMin and localEndMin times for both bookings and requests into their equivalent UTC minute timestamps, using the provided timezoneOffsetMin.
  2. Identify and consolidate any overlapping existing bookings into a minimal set of non-overlapping UTC intervals.
  3. For each resource request, determine if its UTC interval overlaps with any of the consolidated UTC booking intervals.
  4. Return a list of results, indicating the feasibility for each request.

Input & output

Function Signature:

function checkResourceAvailability(bookings: Booking[], requests: Request[]): { requestId: string; feasible: boolean }[]

Input Parameters:

  • bookings: An array of Booking objects. Each Booking object has:
    • localStartMin: number - The start time of the booking in local minutes from a fixed epoch (e.g., 00:00 UTC, Jan 1, 2000).
    • localEndMin: number - The end time of the booking in local minutes from the same epoch.
    • timezoneOffsetMin: number - The offset in minutes from UTC for this booking's timezone. Positive values mean ahead of UTC (e.g., +60 for UTC+1), negative values mean behind UTC (e.g., -300 for UTC-5).
  • requests: An array of Request objects. Each Request object has:
    • requestId: string - A unique identifier for the request.
    • localStartMin: number - The start time of the request in local minutes from the same epoch.
    • localEndMin: number - The end time of the request in local minutes from the same epoch.
    • timezoneOffsetMin: number - The offset in minutes from UTC for this request's timezone.

Return Value:

  • An array of objects, where each object corresponds to a request and has:
    • requestId: string - The identifier of the request.
    • feasible: boolean - true if the request does not overlap with any existing booking, false otherwise. The order of results should match the order of requests in the input.

Clarifications

  • All localStartMin and localEndMin values refer to minutes from the same arbitrary fixed epoch. This simplifies time calculations to basic arithmetic.
  • An interval [start, end) is half-open, meaning start is inclusive and end is exclusive. Overlap occurs if interval1.start < interval2.end AND interval1.end > interval2.start.
  • A booking interval [A, B) and a request interval [C, D) overlap if max(A, C) < min(B, D).

Examples

1

Example 1

Input:

bookings = [ { localStartMin: 60, localEndMin: 120, timezoneOffsetMin: 60 } ], requests = [ { requestId: "req1", localStartMin: 180, localEndMin: 210, timezoneOffsetMin: 0 } ]

Output:

[ { "requestId": "req1", "feasible": true } ]

Note:

Booking: local [60, 120) with offset +60. UTC [60 - 60, 120 - 60) = [0, 60). Request: local [180, 210) with offset 0. UTC [180 - 0, 210 - 0) = [180, 210). The booking is [0, 60) UTC. The request is [180, 210) UTC. They do not overlap. Hence, req1 is feasible.

2

Example 2

Input:

bookings = [ { localStartMin: 60, localEndMin: 120, timezoneOffsetMin: 60 }, { localStartMin: 150, localEndMin: 200, timezoneOffsetMin: 0 } ], requests = [ { requestId: "req2", localStartMin: 0, localEndMin: 70, timezoneOffsetMin: 0 } ]

Output:

[ { "requestId": "req2", "feasible": false } ]

Note:

Booking 1: local [60, 120), offset +60. UTC [0, 60). Booking 2: local [150, 200), offset 0. UTC [150, 200). Consolidated bookings (already non-overlapping): [[0, 60), [150, 200)]. Request: local [0, 70), offset 0. UTC [0, 70). The request [0, 70) overlaps with the first consolidated booking [0, 60) because max(0,0) < min(70,60) => 0 < 60, which is true. Hence, req2 is not feasible.

3

Example 3

Input:

bookings = [ { localStartMin: 600, localEndMin: 720, timezoneOffsetMin: 120 }, { localStartMin: 660, localEndMin: 780, timezoneOffsetMin: 60 } ], requests = [ { requestId: "reqA", localStartMin: 480, localEndMin: 540, timezoneOffsetMin: 0 }, { requestId: "reqB", localStartMin: 600, localEndMin: 660, timezoneOffsetMin: 0 }, { requestId: "reqC", localStartMin: 800, localEndMin: 860, timezoneOffsetMin: 0 } ]

Output:

[ { "requestId": "reqA", "feasible": false }, { "requestId": "reqB", "feasible": false }, { "requestId": "reqC", "feasible": true } ]

Note:

Booking 1: local [600, 720), offset +120. UTC [600 - 120, 720 - 120) = [480, 600). Booking 2: local [660, 780), offset +60. UTC [660 - 60, 780 - 60) = [600, 720). Sorted UTC bookings: [[480, 600), [600, 720)]. Merged UTC bookings: [[480, 720)]. (They touch, so they merge into a single interval)

Request A: local [480, 540), offset 0. UTC [480, 540). Overlaps with merged booking [480, 720): max(480, 480) < min(540, 720) => 480 < 540. True. reqA is not feasible.

Request B: local [600, 660), offset 0. UTC [600, 660). Overlaps with merged booking [480, 720): max(600, 480) < min(660, 720) => 600 < 660. True. reqB is not feasible.

Request C: local [800, 860), offset 0. UTC [800, 860). Overlaps with merged booking [480, 720): max(800, 480) < min(860, 720) => 800 < 720. False. reqC is feasible.

Constraints

Constraints & assumptions

  • 1 <= bookings.length <= 10^4
  • 1 <= requests.length <= 10^4
  • 0 <= localStartMin < localEndMin <= 10^9 for both bookings and requests.
  • -720 <= timezoneOffsetMin <= 840 (representing offsets from -12 hours to +14 hours).
  • requestId strings are unique and non-empty.
  • The system should handle potential edge cases where intervals touch but do not overlap (e.g., [10, 20) and [20, 30) do not overlap) unless explicitly merged by the problem statement (e.g. [10, 20) and [20, 30) would merge to [10, 30) if the problem intends to treat touching intervals as mergeable).

What interviewers evaluate

  • Correctness of UTC Conversion: Accurate translation of local times with offsets to a common UTC reference.
  • Efficient Interval Merging: Ability to correctly and efficiently merge overlapping booking intervals.
  • Optimal Overlap Detection: Implementation of an efficient algorithm to check request feasibility against consolidated bookings.
  • Code Structure and Readability: Clear separation of concerns, well-named variables, and maintainable code.
  • Edge Case Handling: Correct behavior for various interval scenarios (e.g., touching, contained, partial overlap, no overlap).

Loading editor...