Recently, I had to face a challenge to solve a problem that consisted of creating an algorithm to process plane seat reservations and I found a way to solve this problem by using fewer lines of code and with a good performance.

Problem

You are processing plane seat reservations. The plane has N rows of seats, numbered from 1 to N. There are ten seats in each row (labelled from A to K, with letter I omitted), as shown in the figure below:

 

figure-1-plane-seat-reservation

Some of the seats are already reserved. The list of reserved seats is given as a string S (of length M) containing seat numbers separated by single spaces: for example, “1A 3C 2B 40G 5A”. The reserved seats can be listed in S in any order.

Your task is to allocate seats for as many four-person families as possible. A four-person family occupies four seats in one row, that are next to each other – seats across an aisle (such as 2C and 2D) are not considered to be next to each other. It is permissible for the family to be separated by an aisle, but in this case exactly two people have to sit on each side of the aisle. Obviously, no seat can be allocated to more than one family.

Write a function:

class Solution { public int solution(int N, string S)}

that, given the number of rows N and a list of reserved seats as string S, returns the maximum number of four-person families that can be seated in the remaining unreserved seats.

For instance, given N= 2 and S = “1A 2F 1C”, your function should return 2. The following figure shows one possible way of seating two families in the remaining seats:

Given N= 1 and S= “” (empty string), your function should return 2, because we can seta at most two families in a single row of seats, as shown in the figure below:

Your content goes here. Edit or remove this text inline or in the module Content settings. You can also style every aspect of this content in the module Design settings and even apply custom CSS to this text in the module Advanced settings.

Strategy to solve this problem

We know that S contains the list of the seats reserved separated by ” ” (one space), so we can convert this string into a System.collections.generic to perform searches by using LINQ.

List listReserved = new List();
            listReserved = S.Split(' ').ToList();

I have to declare a variable counter to accumulate here when a “key combination occurs”

public int solution(int N, string S)
        {
            int number=1;
            int counter = 0;
            List listReserved = new List();
            listReserved = S.Split(' ').ToList();
            while(number<=N)             {                 if (listReserved.Where(x=> x.Contains(number + "B") || x.Contains(number + "C")|| x.Contains(number + "D")|| x.Contains(number + "E")).FirstOrDefault()==null)
                {
                    listReserved.AddRange(new List{number + "B", number + "C",number + "D" , number + "E"});
                    counter++;
                }

                if (listReserved.Where(x=> x.Contains(number + "F") || x.Contains(number + "G")|| x.Contains(number + "H")|| x.Contains(number + "J")).FirstOrDefault()==null)
                {
                    listReserved.AddRange(new List{number + "F", number + "G",number + "H" , number + "J"});
                    counter++;
                }
                
                if (listReserved.Where(x=> x.Contains(number + "D") || x.Contains(number + "E")|| x.Contains(number + "F")|| x.Contains(number + "G")).FirstOrDefault()==null)
                {
                    listReserved.AddRange(new List{number + "D", number + "E",number + "F" , number + "G"});
                    counter++;
                }
                
                number++;
            }
           
            return counter;
        }

I think that this problem has many ways to be solved, but it is one of them.

I hope you enjoy this code!

Download this code for Github

Abrir chat