2502. Design Memory Allocator

You are given an integer n representing the size of a 0-indexed memory array. All memory units are initially free.

You have a memory allocator with the following functionalities:

1. Allocate a block of size consecutive free memory units and assign it the id mID.
2. Free all memory units with the given id mID.

Note that:

• Multiple blocks can be allocated to the same mID.
• You should free all the memory units with mID, even if they were allocated in different blocks.

Implement the Allocator class:

• Allocator(int n) Initializes an Allocator object with a memory array of size n.
• int allocate(int size, int mID) Find the leftmost block of size consecutive free memory units and allocate it with the id mID. Return the block’s first index. If such a block does not exist, return -1.
• int free(int mID) Free all memory units with the id mID. Return the number of memory units you have freed.

class Allocator {
    vector<int> mem;
    unordered_map<int, vector<int>> mp;
public:
    Allocator(int n) {
        mem = vector<int>(n);
    }

    int allocate(int size, int mID) {
        for(int i = 0, cnt = 0; i < mem.size(); i++) {
            if(mem[i]) cnt = 0;
            else cnt += 1;
            if(cnt == size) {
                for(int j = i - size + 1; j <= i; j++) {
                    mem[j] = mID;
                    mp[mID].push_back(j);
                }
                return i - size + 1;
            }
        }
        return -1;
    }

    int free(int mID) {
        int res = mp[mID].size();
        for(auto idx : mp[mID]) {
            mem[idx] = 0;
        }
        mp.erase(mID);
        return res;
    }
};

/**
 * Your Allocator object will be instantiated and called as such:
 * Allocator* obj = new Allocator(n);
 * int param_1 = obj->allocate(size,mID);
 * int param_2 = obj->free(mID);
 */