lx3
BAN USERpublic class Room
{
public int Capacity { get; set; }
}
public class RoomBooking
{
public int StartTime { get; set; }
public int EndTime { get; set; }
public int NumberOfPeople { get; set; }
}
/// <summary>
/// Greedy assignment
/// </summary>
/// <param name="booking"></param>
/// <returns></returns>
public List<Room> GetRooms(List<RoomBooking> booking)
{
// taken - first argument is the endTime
SortedList<int, Room> takenRooms = new SortedList<int, Room>();
// available - first argument is room capacity
SortedList<int, Room> available = new SortedList<int, Room>();
// sort the timeIntervals
booking = booking.OrderBy(x => x.StartTime).ToList();
foreach (var item in booking)
{
// move rooms from taken to available
int idx = takenRooms.Keys.ToList().BinarySearch(item.StartTime);
if (idx < 0)
idx = (~idx)-1;
if (idx <= takenRooms.Keys.Count - 1)
{
for (int k = idx; k >= 0; k--)
{
available.Add(takenRooms.ElementAt(k).Value.Capacity, takenRooms.ElementAt(k).Value);
takenRooms.RemoveAt(k);
}
}
// if none available - create new
if (available.Count == 0)
{
takenRooms.Add(item.EndTime, new Room() { Capacity = item.NumberOfPeople });
}
else
{
// find first room which satisfies condition and move it from available to taken
available.Keys.ToList().BinarySearch(item.NumberOfPeople);
if (idx < 0)
idx = ~idx;
if (idx < takenRooms.Keys.Count - 1)
{
var room = available.ElementAt(idx);
available.RemoveAt(idx);
takenRooms.Add(item.EndTime, room.Value);
}
else
{
// take the one with the biggest capacity and increase it
var room = available.Last();
available.RemoveAt(available.Count - 1);
room.Value.Capacity = item.NumberOfPeople;
takenRooms.Add(item.EndTime, room.Value);
}
}
}
return takenRooms.Select(x=>x.Value).Union(available.Select(x=>x.Value)).ToList();
}
- lx3 August 07, 2016