Laptop Rentals

Tags

Laptop Rentals

Category

Heaps

Difficulty

Hard

Problem Statement

Given a list of time intervals representing laptop rental periods [start, end), determine the minimum number of laptops needed so that every rental can be accommodated. Two rentals that share an endpoint (one ends at time t, another starts at time t) do not overlap and can use the same laptop.

Intuition

This is the classic interval scheduling / meeting rooms problem. The key insight is that we need a new laptop whenever a new rental starts before any existing rental has ended. Using a min-heap to track the earliest ending rental, we can efficiently check whether a laptop is available: if the earliest end time is at or before the new rental's start time, that laptop can be reused.

Approach

  1. Sort the intervals by start time.
  2. Initialize a min-heap to track end times of active rentals.
  3. For each interval: a. If the heap is non-empty and the minimum end time <= current start time, extract the minimum (that laptop is freed). b. Push the current interval's end time onto the heap.
  4. The size of the heap at the end (or the maximum size during processing) is the answer.

Pseudocode

function laptopRentals(intervals):
    if intervals is empty:
        return 0

    sort intervals by start time

    minHeap = new MinHeap()
    for interval in intervals:
        if minHeap is not empty and minHeap.peek() <= interval.start:
            minHeap.extractMin()
        minHeap.insert(interval.end)

    return minHeap.size()

Time & Space Complexity

  • Time: O(n log n), where n is the number of intervals. Sorting takes O(n log n), and each heap operation is O(log n) for n intervals.
  • Space: O(n) for the heap in the worst case (all intervals overlap).

Key Insights

  • The min-heap always contains the end times of currently active (overlapping) rentals. Its size at any point equals the number of laptops in use.
  • Sorting by start time ensures we process rentals in chronological order.
  • An alternative approach uses a "sweep line": create events for all starts (+1) and ends (-1), sort them, and find the maximum running sum. This also runs in O(n log n).
  • The condition uses <= (not <) because non-overlapping endpoints allow laptop reuse.

Edge Cases

  • No intervals: return 0.
  • Single interval: return 1.
  • All intervals are identical: need n laptops.
  • No intervals overlap: need only 1 laptop.
  • Intervals that touch at endpoints (e.g., [1,5) and [5,10)): only 1 laptop needed.
  • Intervals are already sorted.
  • Intervals with zero duration: still counts as a rental.

Linked mentions