Mixing
Finding the max number of guests in a party for a fixed time
up vote
1
down vote
favorite
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
algorithm
asked Nov 19 at 11:36
TheMri
887
|
show 8 more comments
up vote
1
down vote
favorite
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
algorithm
asked Nov 19 at 11:36
TheMri
887
Possible duplicate of Problem calculating overlapping date ranges
– n.m.
Nov 19 at 11:46
2
Perhaps you should read carefully. The algorithm is perfectly able to compute what you are looking for, with a trivial modification.
– n.m.
Nov 19 at 12:49
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.
2 days ago
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.
2 days ago
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.
2 days ago
|
show 8 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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
algorithm
asked Nov 19 at 11:36
TheMri
887
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
algorithm
algorithm
asked Nov 19 at 11:36
TheMri
887
asked Nov 19 at 11:36
TheMri
887
edited 2 days ago
asked Nov 19 at 11:36
TheMri
887
asked Nov 19 at 11:36
TheMri
887
asked Nov 19 at 11:36
TheMri
887
887
Possible duplicate of Problem calculating overlapping date ranges
– n.m.
Nov 19 at 11:46
2
Perhaps you should read carefully. The algorithm is perfectly able to compute what you are looking for, with a trivial modification.
– n.m.
Nov 19 at 12:49
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.
2 days ago
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.
2 days ago
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.
2 days ago
|
show 8 more comments
Possible duplicate of Problem calculating overlapping date ranges
– n.m.
Nov 19 at 11:46
2
Perhaps you should read carefully. The algorithm is perfectly able to compute what you are looking for, with a trivial modification.
– n.m.
Nov 19 at 12:49
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.
2 days ago
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.
2 days ago
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.
2 days ago
Possible duplicate of Problem calculating overlapping date ranges
– n.m.
Nov 19 at 11:46
Possible duplicate of Problem calculating overlapping date ranges
– n.m.
Nov 19 at 11:46
2
2
Perhaps you should read carefully. The algorithm is perfectly able to compute what you are looking for, with a trivial modification.
– n.m.
Nov 19 at 12:49
Perhaps you should read carefully. The algorithm is perfectly able to compute what you are looking for, with a trivial modification.
– n.m.
Nov 19 at 12:49
1
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.
2 days ago
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.
2 days ago
1
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.
2 days ago
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.
2 days ago
1
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.
2 days ago
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.
2 days ago
|
show 8 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
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)
answered Nov 19 at 12:02
David Winder
2,4511723
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
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)
answered Nov 19 at 12:02
David Winder
2,4511723
add a comment |
up vote
1
down vote
accepted
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)
answered Nov 19 at 12:02
David Winder
2,4511723
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
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)
answered Nov 19 at 12:02
David Winder
2,4511723
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)
answered Nov 19 at 12:02
David Winder
2,4511723
answered Nov 19 at 12:02
David Winder
2,4511723
answered Nov 19 at 12:02
David Winder
2,4511723
answered Nov 19 at 12:02
David Winder
2,4511723
2,4511723
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53373805%2ffinding-the-max-number-of-guests-in-a-party-for-a-fixed-time%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Possible duplicate of Problem calculating overlapping date ranges
– n.m.
Nov 19 at 11:46
2
Perhaps you should read carefully. The algorithm is perfectly able to compute what you are looking for, with a trivial modification.
– n.m.
Nov 19 at 12:49
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.
2 days ago
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.
2 days ago
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.
2 days ago