Algorithm for hours occupied in day by tasks

Question

Edit:
Steps:
Start at target day. 
Then move backwards until no events are carried over from another day.
From there, start counting hours, and keep track of carried over hours. 
Day cannot last more than ActualDayLength()
Then, once you know that, work your way back to target and then calculate actual occupied hours.

I have tasks that are put on a calendar:

Now let me give this some context: Each day 'lasts' 7.5 hours here. But I work with a variable called DayHours (which right now is 7.5). (DayHours is also used in Locked Time which Ill describe below).

The goal of this calendar is to schedule 7.5 hour work days for employees.

What I need, is an algorithm that can correctly tell me how many hours are actually occupied in a day.

This seems simple, but is actually quite recursive.

First, a couple of notes. You will notice Case manager, at 14 hours, could be done in 2 days of 7.5 hours with 1 hour left over. It is stretched to 3 days because 1. Schedule, is 5 hours long, and 2. cannot start until the predecessor tasks of the day are complete.

There is also the concept of Locked Time. In purple is Locked Time. This is a 10 hour block of locked time. This means, on the 12th, I can only do (7.5 - 7.5) hours of work, and Monday, only (7.5 - 2.5) aswell.

I already have a function to calculate an actual day's available hours to account for this:

public decimal GetActualDayLength(DateTime day, Schedule s)
{
    var e = Schedules.GetAllWithElement();
    var t = Timeless(day);
    var locked = from p in e
                 where p.EmployeID == s.EmployeID &&
                 ((p.DateTo.Value.Date) >= t &&
                 Timeless(p.DateFrom.Value) <= t) &&
                 p.IsLocked
                 select p;

    decimal hrs = 0.0M;

    foreach (var c in locked)
    {
        if (c.Hours.Value <= DaysManager.GetDayHours())
            hrs += c.Hours.Value;
        else if (Timeless(c.DateTo.Value) != t)
            hrs += DaysManager.GetDayHours();
        else
        {
            if (c.Hours.Value % DaysManager.GetDayHours() > 0)
                hrs += c.Hours.Value % DaysManager.GetDayHours();
            else
                hrs += DaysManager.GetDayHours();
        }
    }

    return DaysManager.GetDayHours() - hrs;
}

There is also the concept of carry hours.

Here is an example:

Now let us take Thursday the 18th (The 18th has 1. Case):

To find the number of hours this day has for that employee, we need to first look at the tasks that start, end, or fall within that day.

I don't know how many hours I can do on the 18th because the task ending that day might have had carry hours. So I go look at Perform unit test's start day. I cant figure that out either because NWDM finishes that day and it might have carry hours.

So now I go evaluate NWDM. Ahh, this one has nothing ending that day, so I know Schedule will take 5 / 7.5 hours available.

So I keep going, adding 7.5 hours each day that I pass.

Then I get to NWDM's last day. Up until then, I worked 5 + 7.5 + 7.5 + 7.5 hours on it,

So I put in 27.5 hours, so I'll put in (30 - 27.5 = 2.5h) on the 22nd to finish it. So I have 5 hours left to work on Perform Unit Tests.

This means that I will need 1.5h to finish it. Now Case is 1 hour long.

Had case been 7.5 - 1.5 or more, we say the day is full and return DayHours.

Therefore, we are done. The return value is 1.5 + 1 = 2.5.

The function should look a bit like this one:

public decimal GetHours(IEnumerable<Schedule> s, DateTime today)
{
    DateTime t = Timeless(today);

    decimal hrs = 0;
    foreach (Schedule c in s)
    {
        if (c.Hours.Value <= DaysManager.GetDayHours())
            hrs += c.Hours.Value;
        else if (Timeless(c.DateTo.Value) != t)
            hrs += DaysManager.GetDayHours();
        else
        {
            if (c.Hours.Value % DaysManager.GetDayHours() > 0)
                hrs += c.Hours.Value % DaysManager.GetDayHours();
            else
                hrs += DaysManager.GetDayHours();
        }
    }
    return hrs;
}

To get the events that start, end, or fall within a given day, I use:

public IEnumerable<Schedule> GetAllToday(DateTime date, int employeeID, Schedule current)
{
    DateTime t = Timeless(date);
    int sid = current == null ? -1 : current.ScheduleID;

    var e = Schedules.GetAllWithElement();
    return from p in e
           where (((Timeless(p.DateTo.Value) >= t &&
           Timeless(p.DateFrom.Value) <= t &&
           p.EmployeID == employeeID) &&
           (p.IsLocked || (Timeless(p.DateFrom.Value) < t &&
           (sid == -1 ? true : Timeless(p.DateFrom.Value) < current.DateFrom.Value)) ||
           bumpedList.Any(d => d.ScheduleID == p.ScheduleID)) &&
           p.ScheduleID != sid) ||
           ((Timeless(p.DateTo.Value) >= t &&
           (Timeless(p.DateFrom.Value) == t || (Timeless(p.DateFrom.Value) < t &&
           (sid == -1 ? true : Timeless(p.DateFrom.Value) > current.DateFrom.Value))) &&
           p.EmployeID == employeeID) &&
           !p.IsLocked &&
           !bumpedList.Any(d => d.ScheduleID == p.ScheduleID) &&
           p.ScheduleID != sid)) &&
           p.ScheduleID != sid
           select p;
        }

The Schedule has the following relevant fields:

DateFrom
DateTo
Hours
EmployeeID

The Schedule looks something like:

[global::System.Data.Linq.Mapping.TableAttribute(Name="dbo.Schedule")]
public partial class Schedule : INotifyPropertyChanging, INotifyPropertyChanged
{
    private static PropertyChangingEventArgs emptyChangingEventArgs = new PropertyChangingEventArgs(String.Empty);
    private int _ScheduleID;
    private System.Nullable<System.DateTime> _DateFrom;
    private System.Nullable<decimal> _Hours;
    private System.Nullable<int> _EmployeID;
    private System.Nullable<int> _RecurringID;
    private System.Nullable<int> _Priority;
    private System.Nullable<System.DateTime> _DateTo;
    private bool _IsLocked;
    private System.Nullable<int> _BumpPriority;
    private EntitySet<Case> _Cases;
    private EntitySet<Project> _Projects;
    private EntitySet<Task> _Tasks;
    private EntitySet<Task> _Tasks1;
    private EntityRef<Employee> _Employee;
    private EntityRef<Recurring> _Recurring;

    #region Extensibility Method Definitions
    partial void OnLoaded();
    partial void OnValidate(System.Data.Linq.ChangeAction action);
    partial void OnCreated();
    partial void OnScheduleIDChanging(int value);
    partial void OnScheduleIDChanged();
    partial void OnDateFromChanging(System.Nullable<System.DateTime> value);
    partial void OnDateFromChanged();
    partial void OnHoursChanging(System.Nullable<decimal> value);
    partial void OnHoursChanged();
    partial void OnEmployeIDChanging(System.Nullable<int> value);
    partial void OnEmployeIDChanged();
    partial void OnRecurringIDChanging(System.Nullable<int> value);
    partial void OnRecurringIDChanged();
    partial void OnPriorityChanging(System.Nullable<int> value);
    partial void OnPriorityChanged();
    partial void OnDateToChanging(System.Nullable<System.DateTime> value);
    partial void OnDateToChanged();
    partial void OnIsLockedChanging(bool value);
    partial void OnIsLockedChanged();
    partial void OnBumpPriorityChanging(System.Nullable<int> value);
    partial void OnBumpPriorityChanged();
    #endregion

    public Schedule()
    {
        this._Cases = new EntitySet<Case>(new Action<Case>(this.attach_Cases), new Action<Case>(this.detach_Cases));
        this._Projects = new EntitySet<Project>(new Action<Project>(this.attach_Projects), new Action<Project>(this.detach_Projects));
        this._Tasks = new EntitySet<Task>(new Action<Task>(this.attach_Tasks), new Action<Task>(this.detach_Tasks));
        this._Tasks1 = new EntitySet<Task>(new Action<Task>(this.attach_Tasks1), new Action<Task>(this.detach_Tasks1));
        this._Employee = default(EntityRef<Employee>);
        this._Recurring = default(EntityRef<Recurring>);
        OnCreated();
    }
}

Could anyone help me with developing an algorithm that can do this?

Answer 1

Even though you question is very complex and not very clearly explained, I'll try to answer it. Or more precisely hint you how you should decompose and solve it (or how I would solved it).

What I need, is an algorithm that can correctly tell me how many hours are actually occupied in a day.

At first I do not see the real problem in case you have DateTo value available for Schedule. Unless it equals to DateFrom + Hours. In such case it does not reflect the real DateTo but somewhat irrelevant value instead.

I will presume any Schedule is defined by starting time DateFrom and duration Hours. DateTo is calculated value and efficiently computing is the real core of the problem.

So I think this function getting available hours in any time range is pretty straightforward. Speaking in pseudo-code:

TimeSpan GetAvailableTime(DateRange range)
    var tasks = FindIntersectingTasks(range)

    ' now the algorithm which finds available hours on given collection 
    ' of tasks
    ' firstly - we need to determine relevant ranges which intersect 
    '           with given range
    var occupiedRanges = New List<DateRange>(tasks.Count)
    for each task in tasks
        var intersection = range.Intersect(
            new DateRange(task.DateFrom, task.DateTo)
        )

        if Not intersection.IsEmpty
            occupiedRanges.Add(intersection)
        end 
    end 

    ' secondly - sort ranges by start so we can easily merge them
    ranges.Sort(range => range.DateFrom)
    var mergedOccupiedRanges = new List(DateRange)

    ' thirdly - merge ranges so that we have collection with 
    '           non-overlaping ranges (and also sorted)
    for each occupiedRange in occupiedRanges
        ' range may merge only it there is non-empty intersection
        if occupiedRange.CanMerge(mergedOccupiedRanges.Last)
             var mergedRange = range.Merge(mergedOccupiedRanges.Last)
             mergedOccupiedRanges.RemoveLast()
             mergedOccupiedRanges.Add(mergedRange)
        end
    end 

    ' fourthly - it is simple now to determine available/occupied hours
    var timeAvailable = range.Duration
    for each mergedRange in mergedOccupiedRanges
        timeAvailable -= mergedRange.Duration
    end

    return timeAvailable
end

IEnumerable<Schedule> FindIntersectingTasks(DateRange range)
    return From schedule In allEvents
           Where schedule.DateFrom <= range.To 
               And schedule.DateTo >= range.From
end

You may need some adjustments as the DateTime expects normal 24-hour days.