C++ Solution using max heap, improvisations are welcome


#1
void heapify(vector<int> &A,int n,int i)
{
	int root = i;
	int left_child = 2 * i + 1;
	int right_child = 2 * i + 2;
	
	if(left_child < n && A[root] < A[left_child])
		root = left_child;
	
	if(right_child < n && A[root] < A[right_child])
		root = right_child;
	
	if(root != i)
	{
		swap(A[root],A[i]);
		heapify(A,n,root);
	}
}

void heap_sort(vector<int> &A,int n)
{
	for(int i=n/2 - 1;i>=0;i--)
		heapify(A,n,i);
}

int maxProfit(vector<int> row,int people)
{
	int profit = 0;
	do
	{
		heap_sort(row,row.size());
		//not checking if all seats are full in all rows and people are still waiting for a seat
		
		profit += row[0];
		row[0]--;
		people--;
		
	}while(people > 0);
	
	return profit;
}


int Solution::solve(vector<int> &A, int B) {
    return maxProfit(A,B);
}

#2

good but should use stl priority queue for doing implementation questions.