[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 473
  • Last Modified:

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!!!
0
mrichmon
Asked:
mrichmon
  • 7
  • 3
6 Solutions
 
TheAvengerCommented:
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
 
Bob LearnedCommented:
Sometimes it is better to come up with a working example.  

So, here is a start
0
 
Bob LearnedCommented:
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
Bob LearnedCommented:
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)
        {
          double begin1 = evt1.BeginDate.ToOADate();
          double end1 = evt1.EndDate.ToOADate();
          double begin2 = evt2.BeginDate.ToOADate();
          double end2 = evt2.EndDate.ToOADate();

          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);
              overlaps.Add(overlap.Key, overlap);
            }
          }
        }

      }

    }

    return overlaps;

  }

}
0
 
Bob LearnedCommented:
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();

    _maxBegin = Math.Max(_maxBegin, evt1.BeginDate.ToOADate());
    _maxBegin = Math.Max(_maxBegin, evt2.BeginDate.ToOADate());

    _minEnd = Math.Min(_minEnd, evt1.EndDate.ToOADate());
    _minEnd = Math.Min(_minEnd, evt2.EndDate.ToOADate());

    _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;
      return DateTime.FromOADate(_maxBegin);
    }
  }

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

  public int SumOfAttendees
  {
    get { return _sumAttendees; }
  }

}
0
 
Bob LearnedCommented:
Test form:

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

    private void Form1_Load(object sender, EventArgs e)
    {
      myEventList.Add(new MyEvent(1, "1/1/2006", "12/1/2006", 75));
      myEventList.Add(new MyEvent(2, "1/10/2006", "2/10/2006", 20));
      myEventList.Add(new MyEvent(3, "2/1/2006", "6/1/2006", 15));
      myEventList.Add(new MyEvent(4, "5/1/2006", "10/31/2006", 30));
      myEventList.Add(new MyEvent(5, "11/30/2006", "1/1/2007", 50));
      myEventList.Add(new MyEvent(6, "1/1/2006", "1/31/2006", 5));

      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
 
Bob LearnedCommented:
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
 
mrichmonAuthor 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
 
Bob LearnedCommented:
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
 
mrichmonAuthor Commented:
After playing with the solutions, TheAvenger's seemed the simplest to work within our existing framework.

Thanks
0
 
mrichmonAuthor 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

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 7
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now