Function to find Number of customers who could not get a computer

Problem Statement

A cyber cafe has n computers and m customers arrive sequentially. Each customer has a use time duration[i]. A customer gets a computer only if one is available when they arrive. Find the number of customers who could not get a computer.

Example:

• Input: n = 2, arrivals = [1, 2, 3, 4, 5], durations = [3, 3, 3, 3, 3]
• Output: 3
• Explanation:
  • Customer 1 arrives at t=1, uses computer until t=4
  • Customer 2 arrives at t=2, uses computer until t=5
  • Customer 3 arrives at t=3, no computer free → rejected
  • Customer 4 arrives at t=4, computer from customer 1 is free
  • Customer 5 arrives at t=5, computer from customer 2 is free

Approach 1: Brute Force (Simulate with Array)

Intuition

Simulate the process using an array to track when each computer becomes free. For each customer, check if any computer is free at their arrival time.

Algorithm

1. Initialize array of size n to track computer free times (all 0)
2. For each customer:
   • Find a computer that's free (free_time <= arrival_time)
   • If found, update its free time to arrival + duration
   • If not found, increment rejected count
3. Return rejected count

public class Solution {
    public int countRejectedCustomers(int n, int[] arrivals, int[] durations) {
        int m = arrivals.length;
        int[] computerFreeTime = new int[n];
        int rejected = 0;
        
        for (int i = 0; i < m; i++) {
            int arrival = arrivals[i];
            int duration = durations[i];
            
            boolean found = false;
            for (int j = 0; j < n; j++) {
                if (computerFreeTime[j] <= arrival) {
                    computerFreeTime[j] = arrival + duration;
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                rejected++;
            }
        }
        
        return rejected;
    }
}

Complexity Analysis

• Time Complexity: O(n * m) - For each of m customers, check n computers
• Space Complexity: O(n) - Array to track computer free times

Approach 2: Using Min-Heap (Optimal)

Intuition

Use a min-heap to track computer free times. The minimum free time tells us if any computer is available.

Algorithm

1. Initialize min-heap with n zeros (all computers free at t=0)
2. For each customer:
   • Pop minimum free time
   • If min_time <= arrival, computer is available
     • Push new free time (arrival + duration)
   • If min_time > arrival, no computer available
     • Push back the min_time (computer still busy)
     • Increment rejected count
3. Return rejected count

import java.util.*;

public class Solution {
    public int countRejectedCustomers(int n, int[] arrivals, int[] durations) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int i = 0; i < n; i++) {
            minHeap.offer(0);
        }
        
        int rejected = 0;
        
        for (int i = 0; i < arrivals.length; i++) {
            int arrival = arrivals[i];
            int duration = durations[i];
            
            int earliestFree = minHeap.poll();
            
            if (earliestFree <= arrival) {
                minHeap.offer(arrival + duration);
            } else {
                minHeap.offer(earliestFree);
                rejected++;
            }
        }
        
        return rejected;
    }
}

Complexity Analysis

• Time Complexity: O(m log n) - For each customer, heap operations are O(log n)
• Space Complexity: O(n) - Heap of size n

Approach 3: Two Pointer / Sliding Window (When Arrivals are Sequential)

Intuition

If customers arrive sequentially (arrival[i] = i+1), we can use a deque to track which computers become free.

This approach works well when arrivals are in order and we need O(1) check for free computers, but maintaining sorted order in deque makes it O(n) per operation in worst case. The heap approach remains optimal.

String Version of the Problem

Sometimes this problem is given with a string where each character represents a customer:

Dry Run Example

Key Takeaways

1. Min-heap provides efficient O(log n) operations for finding/updating free computers
2. Simulation approach is intuitive but O(n * m)
3. The problem tests understanding of scheduling and resource allocation
4. Similar to meeting rooms problem (can n rooms accommodate m meetings?)
5. Edge case: if n >= m, no one is rejected
6. Can be extended to track which customer used which computer