Student Time scheduling algorithm

I need to find an algorithm to find the best time to meet up for lets say a study group. The system has information about a group of students and their class schedules. The system should give a 开发者_运维问答time for meetup, where there is no conflict with anyone's class schedules. what would be the best way attack this problem. I was looking for any scheduling algorithm, but didnt find anyone that fits.

thanks in advance

Interesting question.

This is what I would do:

1. First, align all timescheduals, for all students (e.g. starting on Mondays, every day devided by 24 hours). You can use a boolean or an integer for each period and store them in an array.
2. Then perform an addition operation on all scheduals together.

Which then looks like this, for example:

Student A: 11100000111111100000
Student B: 00000011111000010001
Student C: 00000000111111110001
_______________________________+
           11100022333222220002
              ^^^          ^^^

Then you'd need to find all gaps in the array (areas with zeros) by using a simple loop which keeps track of the current zero-length. Memoize the start and end index and translate it back (reverse of step 1) to a time region.

this is a matching problem and can be solve by maximum flow algorithm

each student and study group is a node on a directional graph and input for each student have one flow unit as input and is connected to all study groups node. each study node group has unlimited output capacity , when the flow in the network is maximal you have your correct combination

see also Introduction to Algorithms (flow networks chapter)

As I remember the best solutions for this problem are solutions generated by genetic algorithms

see this link http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx

I would start with a very simple approach to this:

• sort all scheduled time blocks from all members of the group into one list, ordered by the start time of a block
• go through the list and merge adjacent items, if they overlap (endTime of n is grater than start time of n+1)

Now your list contains time blocks where all of the group members have other activities. So you need to check the list for free time slots and check, if the slot is large enough for the desired meeting.

Every students has a range of available hours. And everyone has to meet(meaning there is at least one hour where they are all free). You simply start with the first student and intersect its range of available hours with the next student and do that(keep narrowing the original range) for every student and you should be left with a range that fits every student.

I'd set a duration for the meeting and a valid time range when the meeting can occur, i.e. 45 minute duration starting on or after 8:00 AM but not after 9:30 PM. Then it should be a simple matter of intersecting the group member's free time and finding a block that fits. You'll want to include tolerances for overlap, i.e. if 75% of the group can meet then it's viable.

You might also want to include buffers for start/end times to allow for travel, etc. and include those buffers in your search criteria. The one thing I hate about most meetings is that they don't take into account travel/setup time and instead book one meeting right on top of another.

There are 24*60 = 1440 minutes per day. So you could easily brute force it, since you don't need to get more than on a minute basis accuracy. However I'm gonna describe a simple DP.

You can create a boolean array that stores whether that minute has a class in it by one of the students in the group. You also have a second array. This array stores the number of open spaces in this block and to the left. So what you can do is traverse the boolean array from right to left and if the block has a class in it you make the number 0, otherwise you make it 1 plus the number in the minute prior.

However, I feel my explanation lacking, so here is pseudo code:

blocked = <boolean array>;
numtoleft = <array containing the counts>;
if blocked[0]:
    numtoleft[0] = 0;
else:
    numtoleft[0] = 1;

for i = 1 to 1440-1:
    if blocked[i]:
        numtoleft[i] = 0;
    else:
        numtoleft[i] = numtoleft[i-1];

Then you can easily find the biggest open slot by finding the maximum number in the 'numtoleft' array and you can add restrictions to the times you are looking at.

EDIT:

Here's the algorithm in python:

def largestslot(blocked, startminute, endminute):
    numtoleft = [0]*1440
    numtoleft[startminute] = 0 if blocked[startminute] else 1
    for i in xrange(startminute+1, endminute+1):
        numtoleft[i] = 0 if blocked[i] else 1
    ansmax = max(numtoleft[startminute:endminute+1)
    ansi = numtoleft.index(ansmax)
    return (ansi-ansmax, ansi)