2
\$\begingroup\$

This small application is used to approximate conflicts in a schedule. Using a minimal time span of 30 minutes in my example, the application should be able to figure if there's a conflict in +/- 30 minutes range. To compute my approximation, I based my code on this SO's question. The idea is to use bitwise manipulation and, splitting your schedule in parts (30 minutes in my case), attribute one bit to each 30 minutes slot in a day.

Example :

1:00 to 3:00 (AM) = 001111

The first zeros represent the hour from 0:00 to 1:00, then the four other bits represent from 1:00 to 3:00.

1:30 to 4:00 (AM) = 00011111

The three first zeros are from 0:00 to 1:30, then the 5 setted bits are for the timespan of 1:30 to 4:00.

I'm using a long to keep these values, which means that :

\$24hours/day*60minutes/hours= 1440 minutes/day\$

and :

\$1440minutes/30minutes/bit=48bits\$

The last 16 bits of the long are useless (at least, for the moment).

In order to respect my 30 minute TimeSpan, I round my DateTime to respect the said TimeSpan using these methods :

public static class DateTimeExtension
{
    /// <summary>
    /// Rounds down a date according to the timespan
    /// </summary>
    /// <param name="dateTime">DateTime to round</param>
    /// <param name="roundValue">Timespan unit used to round</param>
    /// <returns>Rounded unit</returns>
    /// <example>
    /// 2015/01/01 13:15 with TimeSpan.FromMinute(30) will round to 13:00
    /// </example>
    public static DateTime RoundDown(this DateTime dateTime, TimeSpan roundValue)
    {
        var delta = dateTime.Ticks % roundValue.Ticks;
        return new DateTime(dateTime.Ticks - delta, dateTime.Kind);
    }

    /// <summary>
    /// Rounds up a date according to the timespan
    /// </summary>
    /// <param name="dateTime">DateTime to round</param>
    /// <param name="roundValue">Timespan unit used to round</param>
    /// <returns>Rounded unit</returns>
    /// <example>
    /// 2015/01/01 13:15 with TimeSpan.FromMinute(30) will round to 13:30
    /// </example>
    public static DateTime RoundUp(this DateTime dateTime, TimeSpan roundValue)
    {
        var delta = (roundValue.Ticks - (dateTime.Ticks % roundValue.Ticks)) % roundValue.Ticks;
        return new DateTime(dateTime.Ticks + delta, dateTime.Kind);
    }
}

I'll explain the flow of the program rapidly : We create a Schedule, add ScheduleUnits in it, the call ComputeApproximatedScheduleConflicts() to get an approximation (+/- 30 minutes) of the conflicts using a & operator, then we create a ScheduleConflit per instance of conflict to print the to the console afterwards.

The conflict approximation might need some explaining :

Say I have a ScheduleUnit (call it Unit1) from 1:00 to 3:00 (AM)

And another Schedule Unit (call it Unit2) from 2:30 to 4:30 (AM)

The bit representation of those units are respectively

Unit1 : 001111

Unit2 : 000001111

The bitwise & comparison would result of :

001111 & 000001111 = 000001000

Meaning we have a conflict between 2:30 and 3:00

/// <summary>
/// A schedule unit in time, must start and end on the same day
/// </summary>
public struct ScheduleUnit
{
    public Guid Id { get; }
    public DayOfWeek DayOfWeek { get; }
    public DateTime Start { get; }
    public DateTime End { get; }

    /// <summary>
    /// Builds an instance of the ScheduleUnit class
    /// </summary>
    /// <param name="start">Starting time of the unit</param>
    /// <param name="end">Ending time of the unit</param>
    /// <remarks>Both start and end mus be on the same day.</remarks>
    public ScheduleUnit(DateTime start, DateTime end)
    {
        if(start.DayOfWeek != end.DayOfWeek)
            throw new NotSupportedException("No support for schedule conflict unit on separated days.");

        Id = Guid.NewGuid();
        Start = start;
        End = end;
        DayOfWeek = start.DayOfWeek;
    }
}

/// <summary>
/// A schedule's conflict
/// </summary>
public class ScheduleConflict
{
    public IEnumerable<ScheduleUnit> UnitsInConflict { get; }

    /// <summary>
    /// Builds an instance of the ScheduleConflict class
    /// </summary>
    /// <param name="unitsInConflicts">Units in conflict</param>
    public ScheduleConflict(params ScheduleUnit[] unitsInConflicts)
    {
        UnitsInConflict = new List<ScheduleUnit>(unitsInConflicts);
    }

    public override string ToString()
    {
        return $"Conflict in {String.Join(",",UnitsInConflict.Select(c => c.Id))}{Environment.NewLine}Between { UnitsInConflict.Min(c => c.Start)} and { UnitsInConflict.Min(c => c.End)}";
    }
}

/// <summary>
/// A time schedule that manages conflicts
/// </summary>
public class Schedule
{
    private readonly TimeSpan _minimalUnitTimeSpan;
    public ICollection<ScheduleUnit> ScheduleUnits { get; } 

    /// <summary>
    /// Builds an instance of the Schedule class
    /// </summary>
    /// <param name="minimalUnitTimeSpan">Minimal timespan that an unit can occupy</param>
    public Schedule(TimeSpan minimalUnitTimeSpan)
    {
        _minimalUnitTimeSpan = minimalUnitTimeSpan;
        ScheduleUnits = new List<ScheduleUnit>();
    }

    /// <summary>
    /// Computes an approximation of conflicts in the schedule based on the minimal unit's time span
    /// </summary>
    /// <returns>List of conflicts</returns>
    public IEnumerable<ScheduleConflict> ComputeApproximatedScheduleConflicts()
    {
        List<ScheduleConflict> conflicts = new List<ScheduleConflict>();

        foreach (var dayOfWeek in Enum.GetValues(typeof(DayOfWeek)))
        {
            conflicts.AddRange(ComputeApproximatedScheduleConflictsForADay((DayOfWeek)dayOfWeek));
        }

        return conflicts;
    }

    /// <summary>
    /// Computes an approximation of conflicts for one day in the schedule based on the minimal unit's time span
    /// </summary>
    /// <param name="dayOfWeek">Day of the week to compute</param>
    /// <returns>List of conflicts</returns>
    public IEnumerable<ScheduleConflict> ComputeApproximatedScheduleConflictsForADay(DayOfWeek dayOfWeek)
    {
        var dailyUnits = (from unit in ScheduleUnits
            where unit.DayOfWeek == dayOfWeek
            select new
            {
                ConflictBits = ApproximateConflictBits(unit, _minimalUnitTimeSpan),
                Unit = unit
            }).ToList();

        var copyDailyUnits = dailyUnits.ToList();

        foreach (var dailyUnit in dailyUnits)
        {
            foreach (var dailyUnitCompared in copyDailyUnits)
            {
                //The "AND" operator will find conflicting times.
                long conflicts = dailyUnit.ConflictBits & dailyUnitCompared.ConflictBits;

                if (conflicts == 0 || dailyUnitCompared == dailyUnit) continue;

                yield return new ScheduleConflict(dailyUnit.Unit,dailyUnitCompared.Unit);
            }

            copyDailyUnits.Remove(dailyUnit);
        }
    }

    /// <summary>
    /// Computes an approximation of the conflicts in the schedule using bit shifting.
    /// </summary>
    /// <param name="scheduleUnit">Unit to compute</param>
    /// <param name="minimalUnitTimeSpan">Minimal time span a unit can occupy</param>
    /// <returns>Int64 where setted bits represent a time slot in conflict according to minimal unit timespan</returns>
    /// <example>
    /// Where MinimalUnitTimeSpan = 30
    /// And unit between 1:00 and 3:00
    /// returns : 001111
    /// If units between 1:30 and 4:00
    /// returns : 00011111
    /// </example>
    private static long ApproximateConflictBits(ScheduleUnit scheduleUnit, TimeSpan minimalUnitTimeSpan)
    {
        int startBlocks = (int)(scheduleUnit.Start.TimeOfDay.TotalMinutes) / minimalUnitTimeSpan.Minutes;
        int endBlocks = ((int)(scheduleUnit.End.TimeOfDay.TotalMinutes) / minimalUnitTimeSpan.Minutes) - 1;
        long timeBits = 1;

        for (int i = 0; i < startBlocks; i++)
            timeBits <<= 1;

        long bitPointer = timeBits;
        for (int i = startBlocks; i < endBlocks; i++)
            timeBits |= (bitPointer <<= 1);

        return timeBits;
    }
}

class TimeConflictsFinder
{
    static void Main(string[] c)
    {
        TimeSpan scheduleSpan = TimeSpan.FromMinutes(30);

        DateTime dt1 = new DateTime(2015, 01, 01, 1, 0, 0);
        DateTime dt2 = new DateTime(2015, 01, 01, 1, 30, 0);
        var scheduleUnit1 = new ScheduleUnit(dt1,dt1.AddHours(2));
        var scheduleUnit2 = new ScheduleUnit(dt2,dt2.AddHours(2).AddMinutes(30));

        Schedule schedule = new Schedule(scheduleSpan);
        schedule.ScheduleUnits.Add(scheduleUnit1);
        schedule.ScheduleUnits.Add(scheduleUnit2);

        var conflicts = schedule.ComputeApproximatedScheduleConflicts();

        foreach (var scheduleConflict in conflicts)
        {
            Console.WriteLine(scheduleConflict);
            Console.WriteLine("-------------------------------------------------");
        }

        Console.ReadKey();
    }

}
\$\endgroup\$
  • \$\begingroup\$ Why are you using an approximation? Why not simply represent events as a pair of DateTimes and then list all overlapping ones? \$\endgroup\$ – CodesInChaos Oct 16 '15 at 7:36
  • \$\begingroup\$ I had performance problems before with this approach with large schedules. Also, I'd say it's an exercise with bitwise operators! \$\endgroup\$ – IEatBagels Oct 16 '15 at 13:09
  • \$\begingroup\$ If you choose an appropriate algorithm, the exact solution should be computable in O(n*log(n)) time, i.e. comparable to the cost of sorting the events by their starting time. \$\endgroup\$ – CodesInChaos Oct 16 '15 at 13:16
  • \$\begingroup\$ I should try that out. Actually, if I'm not wrong, my solution works in O(n*log(n)) at the moment, but I should try implementing it with the DateTime's to see the difference. \$\endgroup\$ – IEatBagels Oct 16 '15 at 13:19
3
\$\begingroup\$

Have to run off to a long meeting, but this doesn't look right:

/// <summary>
/// Builds an instance of the ScheduleUnit class
/// </summary>
/// <param name="start">Starting time of the unit</param>
/// <param name="end">Ending time of the unit</param>
/// <remarks>Both start and end mus be on the same day.</remarks>
public ScheduleUnit(DateTime start, DateTime end)
{
    if(start.DayOfWeek != end.DayOfWeek)
        throw new NotSupportedException("No support for schedule conflict unit on separated days.");

    Id = Guid.NewGuid();
    Start = start;
    End = end;
    DayOfWeek = start.DayOfWeek;
}

The comment clearly says the start and end must be the same day and merely checking DayOfWeek does not help much. It could be today (Thursday) and Thursday a week ago. I think you would need to check 2 things:

1) start and end have the same .Kind, and

2) start and end have the same .Date.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.