Queue Reconstruction by Height

Come across this interesting coding example and thought of sharing my experience with this simple solution. 

Basically you have a rectangle array of 2 columns h represents person height and n represents number of tall people who have a height greater than or equal to h.. We need to reconstruct the queue.

Example

Input:

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

My simple solution would be as follow

1. convert array to list of objects (Person class)

2. sort the list by number of tall ahead then by height in ascending order.

3. Go through the list to check/change objects to the correct position of the list.

4. convert the list back to an array

	namespace testsort
	{
	class Program
	{
	static void Main(string[] args)
	{
	Console.WriteLine("Hello World!");
	int[,] mylist = new int[6, 2]; //
	mylist = new int[,] { { 7, 0 }, { 4, 4 }, { 7, 1 }, { 5, 0 }, { 6, 1 }, { 5, 2 } };
	Console.WriteLine("Before Sorting");
	Solution.ShowList(mylist);
	var sortedpeople = new Solution().ReconstructQueue(mylist);
	Console.WriteLine("After Sorting");
	Solution.ShowList(sortedpeople);
	Console.ReadLine();
	}
	}
	public class Solution
	{
	public int[,] ReconstructQueue(int[,] people)
	{
	int[,] sortedpeople = people;
	var personlist = ArrayToList(sortedpeople);
	personlist.Sort(new HeightComparer());
	Console.WriteLine("Initial sort");
	ShowList(ListToArray(personlist));
	var listSize = personlist.Count;
	for (int i = 0; i < listSize; i++)
	{
	var current = personlist[i];
	if (current.numberoftall == 0) continue;
	var maxAheadindex = -1;
	var maxAheadcount = 0;
	for (int j = 0; j < i; j++)
	{
	if (current.numberoftall > 0 && personlist[j].height >= current.height)
	{
	maxAheadindex = j;
	++maxAheadcount;
	}
	if (maxAheadcount > current.numberoftall && maxAheadindex > 0)
	{
	var currentindex = i;
	var newindex = maxAheadindex;
	Shifting(personlist, current, currentindex, newindex);
	//i = newindex;
	break;
	}
	}
	}
	return ListToArray(personlist);
	}
	private void Shifting(List<person> personlist, person current, int currentindex, int newindex)
	{
	personlist.RemoveAt(currentindex);
	personlist.Insert(newindex, current);
	}
	class person
	{
	public int height;
	public int numberoftall;
	public person(int h, int n)
	{
	this.height = h;
	this.numberoftall = n;
	}
	}
	class HeightComparer : IComparer<person>
	{
	public int Compare(person x, person y)
	{
	if (x.numberoftall > y.numberoftall) return 1;
	else if (x.numberoftall < y.numberoftall) return -1;
	else if (x.height > y.height) return 1;
	else if (x.height < y.height) return -1;
	else return 0;
	}
	}
	List<person> ArrayToList(int[,] sortedpeople)
	{
	var list = new List<person>();
	for (int i = 0; i < sortedpeople.GetLength(0); i++)
	{
	list.Add(new person(sortedpeople[i, 0], sortedpeople[i, 1]));
	}
	return list;
	}
	int[,] ListToArray(List<person> list)
	{
	int rows = list.Count;
	int[,] sortedpeople = new int[rows, 2];
	for (int i = 0; i < sortedpeople.GetLength(0); i++)
	{
	sortedpeople[i, 0] = list[i].height;
	sortedpeople[i, 1] = list[i].numberoftall;
	}
	return sortedpeople;
	}
	public static void ShowList(int[,] sortedpeople)
	{
	for (int i = 0; i < sortedpeople.GetLength(0); i++)
	{
	Console.WriteLine(sortedpeople[i, 0] + " , " + sortedpeople[i, 1]);
	}
	}
	}
	}

view raw ReconstructQueue hosted with ❤ by GitHub