# Summing Overlapping periods

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!!!
LVL 35
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
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

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

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

So, here is a start
0
Commented:
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
Commented:
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
Commented:
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
Commented:
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
Commented:
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
Author Commented:
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
Commented:
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
Author Commented:
After playing with the solutions, TheAvenger's seemed the simplest to work within our existing framework.

Thanks
0
Author Commented:
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
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C#

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.