Finding minimum value in given range efficiently

Question

I have function that takes a number n that represents number of servers and another parameter represents a list of requests

Initially servers will hold values 0 of size n.

For each request, requests[i], find the server index which has minimum value in the range [0, requests[i]], store this index into result, also increment the value by one at that server index. If multiple servers have same minimum in range [0, requests[i]] then pick the one that has less index position.

Example:

n = 5 and requests = [3, 2, 3, 2, 4]

Result :

[0,1,2,0,3]

Explanation:

a) requests[0] = 3
n=5 so servers = [0,0,0,0,0]
pick server that has minimum value in range [0, request[0]] = [0,3], the servers in range [0,3] are [0,0,0]
pick server at index 0, and store it in result = [0]. also increment server[0]++ so servers array is now [1,0,0,0,0]

b) requests[1] = 2
servers = [1,0,0,0,0]
pick server that has minimum value in range [0, request[1]] = [0,2], the servers in range [0,2] are [1,0,0]
pick server at index 1, and store it in result = [0, 1]. also increment server[1]++ so servers array is now [1,1,0,0,0]

c) requests[2] = 3
servers[1,1,0,0,0]
range [0,3] => [1,1,0,0]
pick server at index 2, so result = [0,1,2], now servers = [1,1,1,0,0]

d)  requests[3] = 2
servers[1,1,1,0,0]
range [0,2] => [1,1,1]
pick server at index 0, so result = [0,1,2, 0], now servers = [2,1,1,0,0]

e)  requests[4] = 4
servers[2,1,0,0,0]
range [0,4] => [2,1,1,0,0]
pick server at index 3, so result = [0,1,2,0, 3], now servers = [2,1,1,1,0]

Finally result is [0, 1,2,0,3]

Constraints:

1 <= n <= 10^5
0 <= requests[i] < n

Here is my code in O(n^2) time complexity

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println(solve(5, Arrays.asList(3,2,3,2, 4))); //[0,1,2,0,3]
    }
     public static List<Integer> solve(int n, List<Integer> requests) {
        int[] servers = new int[n];
        List<Integer> result = new ArrayList<>();
        for (int e : requests) {
            int min = Integer.MAX_VALUE;
            int idx = -1;
            for (int i = 0; i <= e; i++) {
                if (servers[i] < min) {
                    min = servers[i];
                    idx = i;
                }
            }
            result.add(idx);
            servers[idx]++;
        }
        return result;
    }
    
}

How to solve this in less time complexity?

Answer 1

This can be solved by using a segment tree that stores the lowest index of the minimum value in each node. Updates and queries are both O(log N).