Python Sorted Containers

 

Python does not provide standard library for ordered set or ordered dictionary.

However, there's an Apache2 licensed sorted collections library "SortedContainer".

You can install the library with the following cmd.

pip install sortedcontainers

https://www.geeksforgeeks.org/python-sorted-containers-an-introduction/#:~:text=Sorted%20set%20is%20a%20sorted,must%20be%20hashable%20and%20comparable.

Python sorted containers | An Introduction - GeeksforGeeks

 

The library provides three different containers, which are SortedList, SortedSet, SortedDict.

 

SortedList

.add(value): add a value to the list within O(logN) time.

.update(iterable): update the list with the given iterable in O(k*logN) time.

.remove(value) / .discard(value): removes the value in the list in O(logN) time.

  

SortedList can be very useful when you need to remove elements in the list in an efficient manner.

LeetCode Prob 1606. Find Servers That Handled Most Number of Requests (https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/) is a good example.

In this problem setting, we need to remove elements in idleServers when a server starts working on a request. With default list in Python, removing element would take O(N) time causing inefficiency. A convenient way to deal with such situation would be exploiting the advantage of "SortedList".

from sortedcontainers import SortedList
from bisect import bisect_left
import heapq
class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:

        # (finishTime, serverID)
        schedules = []
        # serverID
        idleServers = SortedList(list(range(k)))
        # current time
        curTime = 0
        # workLoads
        workLoads = [0] * k
        
        for i, (t, l) in enumerate(zip(arrival, load)):
            
            curTime = t
            while schedules and schedules[0][0] <= curTime:
                _, serverID = heapq.heappop(schedules)
                idleServers.add(serverID)
            
            if not idleServers:
                continue
                
            num = i % k
            idx = bisect_left(idleServers, num)
            if idx < len(idleServers):
                serverID = idleServers[idx]
            else:
                serverID = idleServers[0]
            heapq.heappush(schedules, (curTime+l, serverID))
            idleServers.discard(serverID)
            workLoads[serverID] += 1
         
        maxLoad = max(workLoads)
        return [i for i in range(k) if workLoads[i] == maxLoad]