Daily Challenge 10/11/2024: The Number of the Smallest Unoccupied Chair

Party seating simulation.

See the full problem statement on leetcode.

Analysis

times = [[1,4], [2,3], [4,6]]
target = 1

- item: [1,4]
  occupied: {0: 4}
- item: [2, 3]
  occupied: {0: 4, 1: 3}

times = [[3,10],[1,2], [1,3], [1,5],[2,6]]
taget = 0


sorted = [1,2],[1,3],[1,5],[2,6],[3,10]

- item: [1, 2]
  occupied: {0: 2}
  opened: {}

- item: [1, 3]
  occupied: {0: 2, 1: 3}
  opened: {}

- item: [1, 5]
  occupied: {0: 2, 1: 3, 2: 5}
  opened: {}

- item: [2, 6]
  occupied: {0: 6, 1: 3, 2: 5}
  opened: {0}
  note: remove key 0 since its occupant has left

- item: [3, 10]
  occupied: {0: 6, 1: 10, 2: 5}
  opened: {1}

1. Sort by arrival and create a hash table. Record the maximum seat occupied as -1.

2. For all items before arrival of the target:

   • Remove entries in the hash table with the value of the current arrival. Put these values into a queue to be filled.
   • If there are open seats fill the open seat of least value.

Solution

My solution passed, but performed horribly due to its quadratic time complexity. It beat only \(5\%\) in run-time but \(60\%\) in memory. Here it is

class SolutionWorks:
    def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
        occupied: dict[int, int] = {}
        last_time = -1

        final = 0

        for pos, (time, vacates) in sorted(
            enumerate(times), key=lambda items: items[1][0]
        ):
            if time != last_time:
                for k in list(occupied.keys()):
                    if occupied[k] <= time:
                        occupied.pop(k)

            if len(occupied) != final:
                _seat_number = final
                for _seat_number in range(final):
                    if _seat_number not in occupied:
                        break

                seat_number = _seat_number
            else:
                seat_number = final
                final += 1

            if pos == targetFriend:
                return seat_number

            occupied[seat_number] = vacates
            last_time = time

        return -1

I went ahead and read the editorial at this point and learned about min-heaps and noticed that this could optimize my current solution. Doing so only improved the runtime to beat about \(9\%\) and the memory to beat about \(78\%\).

class SolutionMinHeap:

    def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
        occupied: dict[int, int] = {}
        available: list[int] = []
        last_time = -1

        final = 0

        for pos, (time, vacates) in sorted(
            enumerate(times), key=lambda items: items[1][0]
        ):
            if time != last_time:
                for k in list(k for k, v in occupied.items() if v <= time):
                    occupied.pop(k)
                    heapq.heappush(available, k)

            if available:
                seat_number = heapq.heappop(available)
            else:
                seat_number = final
                final += 1

            if pos == targetFriend:
                return seat_number

            occupied[seat_number] = vacates
            last_time = time

        return -1

The obvious problem with the above solution is the time spent searching for values to remove from occupied - this is why this solution has quadratic time complexity. The editorial solution solves this by breaking each event into arrival and leaving events. My rendition of this solution beat about \(38\%\) in runtime and \(60\%\) in memory.

class Solution:

    def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:

        events = []
        for index, (time_start, time_stop) in enumerate(times):
            events.append([time_start, index])
            events.append([time_stop, ~index])

        events.sort(key=lambda pair: pair[0])

        vacant = list(range(len(times)))
        occupied: list[tuple[int, int]] = list()

        for time, pos in events:

            # Mark all chairs as vacated for the friends which have left.
            while occupied and occupied[0][0] <= time:
                _, vacated_index = heapq.heappop(occupied)
                heapq.heappush(vacant, vacated_index)

            # Mark chair occupied if the friend is ariving.
            if pos > -1:
                vacant_index = heapq.heappop(vacant)
                heapq.heappush(occupied, (times[pos][1], vacant_index))

                if pos == targetFriend:
                    return vacant_index

        return -1