Solved

# Summing Overlapping periods

Posted on 2006-04-03
469 Views
If I have a list of events:

class MyEvent
{
int eventID;
DateTime beginDate;
DateTime endDate;
int attendees;
}

List<MyEvent> myEventList;

Now I need to iterate over all the events in myEventList and find any overlapping periods where the sum of attendees is greater than 100.  I need to end up with at the minimum, the IDs of the events that cause the sum of the attendees to be greater than 100.  An added bonus would be to know the exact date range where that occurs.

Example events:

1    1/1/2006       12/1/2006      75
2    1/10/2006     2/10/2006      20
3    2/1/2006       6/1/2006       15
4    5/1/2006       10/31/2006    30
5    11/30/2006    1/1/2007       50
6    1/1/2006       1/31/2006      5

So the results I would want generated would be
Events 1,2,3 overlap with a sum of 110 from 2/1/2006 to 2/10/2006
Events 1,3,4 overlap with a sum of 120 from 5/1/2006 to 6/1/2006
Events 1,4 overlap with a sum of 105 from 5/1/2006 to 10/31/2006
Events 1,5 overlap with a sum of 125 from 11/30/2006 to 12/1/2006

If you can't get me the sum or the exact date range that is okay, as long as I have all the event IDs, but as much of that infor as possible is preferred.

Any help with an algorithm to do this is greatly appreciated!!!
0
Question by:mrichmon

LVL 20

Accepted Solution

Try sorting the events based on their start date. Then go over the sorted list and for every start/end date of an event check how many events are there which are active on this date. Sum the number of participant to find out if the criteria are ok. The sorting can help you make a better performance during the search of events
0

LVL 96

Expert Comment

Sometimes it is better to come up with a working example.

So, here is a start
0

LVL 96

Assisted Solution

MyEvent:

using System;
using System.Collections.Generic;
using System.Text;

public class MyEvent
{
private int _eventID;
private DateTime _beginDate;
private DateTime _endDate;
private int _attendees;

public MyEvent(int id, string begin, string end, int attendees)
{
_eventID = id;
_beginDate = DateTime.Parse(begin);
_endDate = DateTime.Parse(end);
_attendees = attendees;
}

public int EventID
{
get { return _eventID; }
}

public DateTime BeginDate
{
get { return _beginDate; }
}

public DateTime EndDate
{
get { return _endDate; }
}

public int Attendees
{
get { return _attendees; }
}

}
0

LVL 96

Assisted Solution

OverlapChecker:

using System;
using System.Collections.Specialized;
using System.Collections.Generic;
using System.Text;

public class OverlapChecker
{

public static HybridDictionary Check(List<MyEvent> events)
{

HybridDictionary overlaps = FindOverlaps(events);

return overlaps;

}

private static HybridDictionary FindOverlaps(List<MyEvent> events)
{

HybridDictionary overlaps = new HybridDictionary();

foreach (MyEvent evt1 in events)
{

foreach (MyEvent evt2 in events)
{

if (evt1.EventID != evt2.EventID)
{

if ((begin2 >= begin1 && begin2 <= end1) ||
(end2 >= begin1 && end2 <= end1))
{
string reverseKey = evt2.EventID + "," + evt1.EventID;
if (!overlaps.Contains(reverseKey))
{
EventOverlap overlap = new EventOverlap(evt1, evt2);
}
}
}

}

}

return overlaps;

}

}
0

LVL 96

Assisted Solution

EventOverlap:

using System;
using System.Collections.Generic;
using System.Text;

public class EventOverlap
{
private string _id1 = "";
private string _id2 = "";
private double _maxBegin = int.MinValue;
private double _minEnd = int.MaxValue;
private int _sumAttendees;

public EventOverlap (MyEvent evt1, MyEvent evt2)
{
_id1 = evt1.EventID.ToString();
_id2 = evt2.EventID.ToString();

_sumAttendees += (evt1.Attendees + evt2.Attendees);
}

public string Key
{
get { return _id1 + "," + _id2; }
}

public string Id1
{
get { return _id1 ; }
}

public string Id2
{
get { return _id2; }
}

public DateTime BeginDate
{
get
{
if (_maxBegin == int.MinValue)
return DateTime.MinValue;
}
}

public DateTime EndDate
{
get
{
if (_minEnd == int.MaxValue)
return DateTime.MaxValue;
}
}

public int SumOfAttendees
{
get { return _sumAttendees; }
}

}
0

LVL 96

Assisted Solution

Test form:

private List<MyEvent> myEventList = new List<MyEvent>();

private void Form1_Load(object sender, EventArgs e)
{

HybridDictionary results = OverlapChecker.Check(myEventList);

foreach (EventOverlap result in results.Values)
{
Console.WriteLine("IDs: {0},{1}  Begin: {2}  End: {3}  Count: {4}",
result.Id1, result.Id2, result.BeginDate.ToShortDateString(),
result.EndDate.ToShortDateString(), result.SumOfAttendees);
}
0

LVL 96

Assisted Solution

Test results:

IDs: 1,2  Begin: 1/10/2006  End: 2/10/2006  Count: 95
IDs: 1,3  Begin: 2/1/2006  End: 6/1/2006  Count: 90
IDs: 1,4  Begin: 5/1/2006  End: 10/31/2006  Count: 105
IDs: 1,5  Begin: 11/30/2006  End: 12/1/2006  Count: 125
IDs: 1,6  Begin: 1/1/2006  End: 1/31/2006  Count: 80
IDs: 2,3  Begin: 2/1/2006  End: 2/10/2006  Count: 35
IDs: 2,6  Begin: 1/10/2006  End: 1/31/2006  Count: 25
IDs: 3,4  Begin: 5/1/2006  End: 6/1/2006  Count: 45

Does all this look right for a first pass?

Bob
0

LVL 35

Author Comment

Well,

I have been working with the idea posted by TheAvengor.  It seems sound reasoning to only have to check start and end dates - basically end points - to deterime if there is one.  But it doesn't seem that the list needs to be sorted - that doesn't appear to add any necessary function, but you could end loops earlier if they were sorted I guess - so it probably adds efficiency.

As for that code Bob,

Very interesting!  I have not seen the HybridDictionary before.  I'll have to take some time to look at it further, but the one thing I did notice is that in your test results it is catching overlaps caused by 2 events, but overlaps over 100 could be caused by any number of events.  You have 2 results over 100.  Notice in my sample results there were 4 results over 100 - 2 of which were caused by the sum of more than 2 events.

I will take some time to play with this in the next day or so.  ANy further comments appreciated :o)
0

LVL 96

Expert Comment

This is an interesting problem, and I was only trying to see if it was something easily accomplished.  I went through a few iterations of different solutions.  I was thinking about a multi-pass system, so that attempt was pass #1.  I just wanted to make sure that the logic and reasoning was sound before continuing.

It was an attempt just to compare 2 events to see if they overlap.  Then, take the overlapped events, and test them for overlaps.  Ultimately, this may not be the most efficient method, but sometimes you just need to find something that works first, and then tinker later.

Bob
0

LVL 35

Author Comment

After playing with the solutions, TheAvenger's seemed the simplest to work within our existing framework.

Thanks
0

LVL 35

Author Comment

But we determined that the list did not have to be sorted and we only had to check start points.  We then created overlap sets and were able to do operations based off of the overlap sets (basically multi-dimensional arrays)
0

## Featured Post

This article introduced a TextBox that supports transparent background.   Introduction TextBox is the most widely used control component in GUI design. Most GUI controls do not support transparent background and more or less do not have the…
It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…
Hi everyone! This is Experts Exchange customer support.  This quick video will show you how to change your primary email address.  If you have any questions, then please Write a Comment below!
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…