2

Given 2 Lists that indicates the arriving time and leaving time of each guest to a party how can I find the largest number of guests (or who they'r) that hangs together for at least minTime seconds?

Example:

Input:

List<float> ArrivingList = {3,2,8,12,5};
List<float> LevingList =   {17,7,19,15,11};
int minTime = 4;

Meaning that first guest arrives at time 3 and leave at time 17, second guest arrives at time 2 and leave at time 7. etc...

Output: {0,1}; //Or {0,4} both are correct for this example.

I know how to solve it without the minTime demand, but this version I just couldn't figure out.

EDIT: Please note that my question is NOT a duplicate of this one. I'm looking for the maximum number of guests that DO overlap AND for a defined period of time.

Edit 2 My goal is to get the largest overlapping subset of the guests that spends minTime together. Example 2: Input:

List<float> ArrivingList = {1,2,3};
List<float> LevingList =   {4,5,6};
int minTime = 3;

Consider the interval (2,5). Even though there is an overlap of 3 seconds it's not continues and switch between guest #0 and guest #2.

 `Output:` {0};// or {1} or {2} because all of the guests spends the min time some time but never together
TheMri
  • 1,217
  • 8
  • 12
  • Possible duplicate of [Problem calculating overlapping date ranges](https://stackoverflow.com/questions/7468948/problem-calculating-overlapping-date-ranges) – n. m. could be an AI Nov 19 '18 at 11:46
  • @n.m. it's not a duplicate. Actually we're looking for the exact opposite. Please read carefully. – TheMri Nov 19 '18 at 12:16
  • @TheMri does my post answer you or you want the number of maximum guests that overlap? not just all the pairs? – dWinder Nov 19 '18 at 12:48
  • 2
    Perhaps *you* should read carefully. The algorithm is perfectly able to compute what you are looking for, with a trivial modification. – n. m. could be an AI Nov 19 '18 at 12:49
  • @DavidWinder your [answer](https://dotnetfiddle.net/R73ukX) seems to solve it! I'm now trying to reduce the time complexity. Thanks! – TheMri Nov 19 '18 at 13:04
  • @n.m. So please, write down this "trivial modification". Not only that I'm looking for the exact opposite but also I have another constraint. If you know the solution, please, share it with me. – TheMri Nov 19 '18 at 13:08
  • I cannot possibly know about your "other constraint" until you spell it out in the question. – n. m. could be an AI Nov 19 '18 at 13:31
  • 1
    As for the trivial modification, consider this. When you see a closing bracket in a bracket counting algorithm, you know the nesting level (that would be the number of guests in your application), and you know where the closing brace is (what is the time of a guest leaving in your application), but you don't know where the corresponding opening brace is (the time of a guest arriving in your application). If you knew the arrival time, you could easily calculate the interval duration, and weed out intervals which are too small. Right? – n. m. could be an AI Nov 19 '18 at 13:31
  • @n.m. Thanks for a helpful comment. Yes, what you'r saying is right. Weeding out too small duration is trivial as I know the arrive and leave time for each guest and the 'minTime' needed (BTW this is the other constraint i was referring earlier). However consider the following: In the example in my question guest #3 (arrives at 12 leaves at 15) is the only one with a duration smaller then 'minTime' however, in spite of the fact that there are times where 3 other guest are in the party at the same time the largest group fulfills all requirements is of size 2. – TheMri Nov 19 '18 at 14:10
  • 1
    Now that I read your question again I see an ambiguity. Suppose you have this arrival-departure times: {1,2,3},{4,5,6} and min time is 3. You have an interval (2,5) during which at least 2 guests are present at any given moment, but they are not the same 2 guests throughout the interval. What should be the answer in this instance? – n. m. could be an AI Nov 19 '18 at 14:29
  • @n.m. at the (2,5) interval only guest #1 (arrive at 2 leave at 5) spends the require min time so over all the answer should be a singleton (or a list of singletons, depends on the implementation), Because all of the guests spends the min time some time but never together. – TheMri Nov 19 '18 at 14:46
  • 1
    Please update your question with this example and explain why the answer should be as you describe, because it is not quite apparent from the current wording. And yes, the bracket counting algorithm would be tricky to modify for this problem. It is possible but the time complexity is not great. Let me think about it a bit. – n. m. could be an AI Nov 19 '18 at 14:50
  • Also please clarify what you need, the largest overlapping *subset* of the guests or the list of overlapping *pairs* as in @DavidWinder answer . These are totally different things. – n. m. could be an AI Nov 19 '18 at 14:52

1 Answers1

2

I guess you can use the following algorithm:

Init answer as empty array
For each pair of guess i,j:
    OverlapTime = min(leaving(i),leaving(j)) - max(arriving(i),arriving(j))
    If overlapTime >= minTime:
        Push (i,j) to answer array

This will be O(n^2)

dWinder
  • 11,597
  • 3
  • 24
  • 39