Solve Three Algorithmic Tasks

You were asked three coding problems:

1. Count events inside a time window

   • You are given an initial collection of event timestamps in HH:MM:SS format.
   • The timestamps may be unsorted and may contain duplicates.
   • Design a data structure that supports preprocessing and a query function:
     • build(events): preprocess the events.
     • query(start_time, end_time): return how many events fall within the inclusive range [start_time, end_time].
   • Example:
     • events = ["12:00:01", "01:02:02", "03:03:03"]
     • query("01:02:01", "01:02:03") -> 1
     • query("01:00:00", "04:00:00") -> 2

2. Form a target string from double-sided cards

   • You are given cards where each card has one lowercase English letter on the front and one on the back.
   • Each card can be used at most once, and if used, you may choose only one side.
   • Determine whether the target string can be formed using the available cards.
   • Example:
     • cards = [["a", "b"], ["c", "d"]]
     • target = "ac" -> true
     • target = "ab" -> false because both a and b are on the same card.

3. Merge multiple sorted lists

   • You are given N sorted lists of integers.
   • Merge them into one fully sorted output list.
   • The goal is to do better than concatenating everything and sorting again.

Part 1: Count Events Inside Inclusive Time Windows

You are given a list of event timestamps from a single day, each in 'HH:MM:SS' format. The timestamps may be unsorted and may contain duplicates. You are also given several query windows. For each query [start_time, end_time], return how many events fall inside the inclusive range. Your function should preprocess the events once and answer all queries efficiently.

Constraints

• 0 <= len(events), len(queries) <= 200000
• Each timestamp is a valid time from '00:00:00' to '23:59:59'
• Event timestamps may be unsorted and may contain duplicates
• If a query has start_time > end_time, treat its answer as 0

Examples

Example 1

Input: (['12:00:01', '01:02:02', '03:03:03'], [('01:02:01', '01:02:03'), ('01:00:00', '04:00:00')])
Output: [1, 2]

Explanation: Only '01:02:02' is inside the first window. The second window includes '01:02:02' and '03:03:03'.

Example 2

Input: (['00:00:00', '23:59:59', '12:30:30', '12:30:30'], [('12:30:30', '12:30:30'), ('00:00:00', '23:59:59'), ('13:00:00', '14:00:00')])
Output: [2, 4, 0]

Explanation: The exact-time query counts both duplicates. The full-day query counts all events. The last window contains none.

Hints

1. Convert each timestamp into seconds since midnight so comparisons become integer comparisons.
2. After sorting the converted event times, use binary search to find how many values fall between the two endpoints.

Part 2: Form a Target String from Double-Sided Cards

You are given double-sided cards. Each card contains one lowercase English letter on the front and one lowercase English letter on the back. You may use each card at most once, and if you use a card you may choose only one of its two letters. Determine whether it is possible to form the target string exactly.

Constraints

• 0 <= len(cards) <= 500
• 0 <= len(target) <= 500
• Each letter is a lowercase English letter
• A card like ['a', 'a'] can still be used at most once, so it contributes only one 'a'

Examples

Example 1

Input: ([['a', 'b'], ['c', 'd']], 'ac')
Output: True

Explanation: Use 'a' from the first card and 'c' from the second card.

Example 2

Input: ([['a', 'b'], ['c', 'd']], 'ab')
Output: False

Explanation: Both 'a' and 'b' are on the same card, but a card can be used only once.

Hints

1. Think of each needed target character as needing to be assigned to a distinct card that contains that letter.
2. This can be solved as a bipartite matching problem between target positions and cards.

Part 3: Merge Multiple Sorted Lists

You are given N sorted lists of integers. Merge them into one fully sorted list. The goal is to do better than concatenating all numbers and sorting again.

Constraints

• 0 <= len(lists) <= 100000
• 0 <= total number of integers across all lists <= 200000
• Each individual list is already sorted in non-decreasing order
• Values may be negative and duplicates are allowed

Examples

Example 1

Input: ([[1, 4, 5], [1, 3, 4], [2, 6]])
Output: [1, 1, 2, 3, 4, 4, 5, 6]

Explanation: Repeatedly taking the smallest front element across the lists produces the fully merged order.

Example 2

Input: ([[], [0], [], [0, 2]])
Output: [0, 0, 2]

Explanation: Empty inner lists should be ignored.

Hints

1. Keep track of the current smallest unused element from each list.
2. A min-heap lets you repeatedly extract the next smallest value efficiently.