c# - Slot Allocation Algorithm -

c# - Slot Allocation Algorithm -

is there generic algorithm can employ solve next problem:

given:

background: month, has 0 1000 events (any number really). each event has start , end dates. events take place in rooms, 1 @ time (no overlaps, consequent events allowed share end , start dates each other). number of rooms unlimited.

the challenge: allocate rooms events such number of rooms required host monthly events kept minimum.

while finish solution highly appreciated i'm looking directions, smart ideas.

class event: - int id; - datetime startdate; - datetime enddate class allocation: - int eventid - int roomid

so i'm looking for:

// roomids enumerable.range(1, int.maxvalue) ienumerable<allocation> getallocations(ienumerable<event> events, ienumerable<int> roomids, int year, int month) { ... }

split every event 2 timepoints labeled 'start' , 'end' (keeping pointer original event), sort points on time - break ties 'end's come before 'start's same time.

now go on points (in order defined above), allocating first free number on each 'start' , freeing associated number on each 'end'.

example:

events: 9am-5pm, 9am-2pm, 5pm-6pm, 3pm-6pm

sorted table of timepoints:

(9am start event1), (9am start event2), (2pm end event 2), (3pm start event4), (5pm end event1), (5pm start event3), (6pm end event3), (6pm end event4)

processing:

(9am start event1) - assign room 1 event1 (9am start event2) - assign room 2 event2 (2pm end event2) - free room 2 (3pm start event4) - assign room 2 event4 (5pm end event1) - free room 1 (5pm start event3) - assign room 1 event3 (6pm end event3) - free room 1 (6pm end event4) - free room 2

c# algorithm