LEARNING JOURNAL

interface Task {
    val: string,
    freq: number
}

function leastInterval(tasks: string[], n: number): number {
    const hashTB:Record<string, number> = {};

    for(let i = 0; i < tasks.length; i++) {
        if(hashTB[tasks[i]] === undefined) {
            hashTB[tasks[i]] = 1
        }
        else {
            hashTB[tasks[i]]++;
        }
    }

    let i = n + 1;

    const heap = new MaxHeap(hashTB);
    const result:(Task|null)[] = [];

   while(!heap.isEmpty()) {
        const remainingArr:Task[] = [];

        while(i > 0 && !heap.isEmpty()) {
            const task = heap.pop();
            result.push(task);

            task.freq--;

            if(task.freq > 0) {
                remainingArr.push(task);
            }

            i--;
        }

        if(i > 0 && remainingArr.length > 0) {
            while(i > 0){
                result.push(null);
                i--;
            }
        }
       
        for(let iA = 0; iA < remainingArr.length; iA++) {
            heap.push(remainingArr[iA]);
        }

        i = n + 1;
   }


   return result.length;
};

class MaxHeap {
    private arr:Task[] = [];

    constructor(hashTB:Record<string, number>) {
        const tasks:Task[] = Object.keys(hashTB).map(key => ({freq: hashTB[key], val:key}));


        for(let i = 0; i < tasks.length; i++){
            this.push(tasks[i]);
        }
    }

    isEmpty():boolean {
        return this.arr.length === 0;
    }

    
    push(task:Task) {
        this.arr.push(task);

        let curI = this.arr.length - 1,
            parentI = this.getParentI(curI);
        
        while(curI > 0 && this.arr[curI].freq > this.arr[parentI].freq){
            this.swap(curI, parentI);
            curI = parentI;
            parentI = this.getParentI(curI);
        }

    }
    
    pop():Task {
        const retVal = this.arr[0];

        const last = this.arr.pop();

        if(this.arr.length === 0) return retVal;

        this.arr[0] = last;
        let curI = 0;    
        let leftChildI = this.getLeftChildI(curI),
            rightChildI = this.getRightChildI(curI);

        while((leftChildI < this.arr.length  && this.arr[leftChildI].freq > this.arr[curI].freq) ||
        (rightChildI < this.arr.length  && this.arr[rightChildI].freq > this.arr[curI].freq) ) {
            const greaterChildI = rightChildI < this.arr.length && this.arr[rightChildI].freq > this.arr[leftChildI].freq ?
                                        rightChildI : leftChildI;

            this.swap(curI, greaterChildI);

            curI = greaterChildI;
            leftChildI = this.getLeftChildI(curI);
            rightChildI = this.getRightChildI(curI);
        }    


        return retVal;
    }

    private swap(i1:number, i2:number) {
        const temp = this.arr[i1];
        this.arr[i1] = this.arr[i2];
        this.arr[i2] = temp;
    }

    private getParentI(i:number) {
        return Math.floor((i - 1)/2);
    }

    private getLeftChildI(i:number) {
        return i*2 + 1;
    }

    private getRightChildI(i:number) {
        return i*2 + 2;
    }
}