Find a point shared by maximum segments
$begingroup$
Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$.
Example:
Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]
You can represent them as [min, max]---it is equivalent:
Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]
How can I find an integer that belongs to the maximum amount of segments? For the given example, it is 1.
I look for the most efficient algorithm.
algorithms time-complexity arrays
edited Mar 19 at 11:30
xskxzr
3,93121033
asked Mar 19 at 9:33
Vladimir NabokovVladimir Nabokov
1382
New contributor
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$.
Example:
Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]
You can represent them as [min, max]---it is equivalent:
Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]
How can I find an integer that belongs to the maximum amount of segments? For the given example, it is 1.
I look for the most efficient algorithm.
algorithms time-complexity arrays
edited Mar 19 at 11:30
xskxzr
3,93121033
asked Mar 19 at 9:33
Vladimir NabokovVladimir Nabokov
1382
New contributor
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$.
Example:
Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]
You can represent them as [min, max]---it is equivalent:
Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]
How can I find an integer that belongs to the maximum amount of segments? For the given example, it is 1.
I look for the most efficient algorithm.
algorithms time-complexity arrays
edited Mar 19 at 11:30
xskxzr
3,93121033
asked Mar 19 at 9:33
Vladimir NabokovVladimir Nabokov
1382
New contributor
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$.
Example:
Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]
You can represent them as [min, max]---it is equivalent:
Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]
How can I find an integer that belongs to the maximum amount of segments? For the given example, it is 1.
I look for the most efficient algorithm.
algorithms time-complexity arrays
algorithms time-complexity arrays
edited Mar 19 at 11:30
xskxzr
3,93121033
asked Mar 19 at 9:33
Vladimir NabokovVladimir Nabokov
1382
New contributor
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Mar 19 at 11:30
xskxzr
3,93121033
asked Mar 19 at 9:33
Vladimir NabokovVladimir Nabokov
1382
New contributor
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Mar 19 at 11:30
xskxzr
3,93121033
edited Mar 19 at 11:30
xskxzr
3,93121033
edited Mar 19 at 11:30
xskxzr
3,93121033
3,93121033
asked Mar 19 at 9:33
Vladimir NabokovVladimir Nabokov
1382
New contributor
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 19 at 9:33
Vladimir NabokovVladimir Nabokov
1382
asked Mar 19 at 9:33
Vladimir NabokovVladimir Nabokov
1382
1382
New contributor
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Vladimir Nabokov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)
Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:
(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)
Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.
(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1
This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.
answered Mar 19 at 10:12
VincenzoVincenzo
1,9171614
$endgroup$
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
Mar 19 at 11:29
1
$begingroup$
As endpoints are bounded integers, you even can skip the sort phase and just count the number of "in" and "out" on every position (4 K integers).
$endgroup$
– Vince
Mar 19 at 13:44
$begingroup$
@Vince you have to account for closed/open interval ends. That's what the 4 in 4 K is, I guess?
$endgroup$
– John Dvorak
Mar 19 at 17:27
$begingroup$
Thanks. My problem that the answer is looking like a voodoo. It does resolve the problem, but there is no explanation that could explain it properly. Tentatively, I explain it to myself by following: "going from left to right, we raise the count, finding common points, while more and more segments starting and adding to each other like a Union..; going from right to left we do the same, but raise the counter if this direction contains more common points than previous direction... ", but it is quite obsure why this "directions competition" brings the right result...Not easy...
$endgroup$
– Vladimir Nabokov
Mar 20 at 8:15
$begingroup$
@VladimirNabokov, the main idea is that in the second phase, the count variable at a given point equals the number of segments intersecting that point. By the way, there is only one traversal, from left to right. I think it will be easy to understand the algorithm if you first understand why it works for the cases of one segment only, and two segments only.
$endgroup$
– Vincenzo
Mar 20 at 10:19
|
show 1 more comment
$begingroup$
Let's build an array of size 2*k+1 all initialized with 0. For each segment of the form [L, R], we will add 1 at Lth index and subtract 1 from R+1th index.
Note : We add K to every values to shift the range from -K to +K to 0 to 2*K.
Now to obtain the result, we will perform a prefix sum.
array[i] = array[i-1] + array[i], where 1 <= i <= 2*K ( assuming 0-based indexing)
Let i be the index with maximum value. Then answer will be i-K.
Let us solve the asked example :
Let K = 5 and segments are [-2, 3], [1, 5] and [-3, 1]. Then after adding K the segments become
[3, 8], [6, 10] and [2, 6].
On performing the +1 and -1 updates our array will be
[0, 0, 1, 1, 0, 0, 1, -1, 0, -1, 0, -1].
Prefix sum will result into
[0, 0, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0].
Hence the index with max value is 6 and hence answer will be 6 - 5 = 1.
Time complexity of above approach will be O(max(N, K)).
answered Mar 20 at 7:31
Shiv ShankarShiv Shankar
362
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Vladimir Nabokov is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcs.stackexchange.com%2fquestions%2f105773%2ffind-a-point-shared-by-maximum-segments%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)
Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:
(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)
Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.
(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1
This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.
answered Mar 19 at 10:12
VincenzoVincenzo
1,9171614
$endgroup$
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
Mar 19 at 11:29
1
$begingroup$
As endpoints are bounded integers, you even can skip the sort phase and just count the number of "in" and "out" on every position (4 K integers).
$endgroup$
– Vince
Mar 19 at 13:44
$begingroup$
@Vince you have to account for closed/open interval ends. That's what the 4 in 4 K is, I guess?
$endgroup$
– John Dvorak
Mar 19 at 17:27
$begingroup$
Thanks. My problem that the answer is looking like a voodoo. It does resolve the problem, but there is no explanation that could explain it properly. Tentatively, I explain it to myself by following: "going from left to right, we raise the count, finding common points, while more and more segments starting and adding to each other like a Union..; going from right to left we do the same, but raise the counter if this direction contains more common points than previous direction... ", but it is quite obsure why this "directions competition" brings the right result...Not easy...
$endgroup$
– Vladimir Nabokov
Mar 20 at 8:15
$begingroup$
@VladimirNabokov, the main idea is that in the second phase, the count variable at a given point equals the number of segments intersecting that point. By the way, there is only one traversal, from left to right. I think it will be easy to understand the algorithm if you first understand why it works for the cases of one segment only, and two segments only.
$endgroup$
– Vincenzo
Mar 20 at 10:19
|
show 1 more comment
$begingroup$
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)
Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:
(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)
Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.
(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1
This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.
answered Mar 19 at 10:12
VincenzoVincenzo
1,9171614
$endgroup$
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
Mar 19 at 11:29
1
$begingroup$
As endpoints are bounded integers, you even can skip the sort phase and just count the number of "in" and "out" on every position (4 K integers).
$endgroup$
– Vince
Mar 19 at 13:44
$begingroup$
@Vince you have to account for closed/open interval ends. That's what the 4 in 4 K is, I guess?
$endgroup$
– John Dvorak
Mar 19 at 17:27
$begingroup$
Thanks. My problem that the answer is looking like a voodoo. It does resolve the problem, but there is no explanation that could explain it properly. Tentatively, I explain it to myself by following: "going from left to right, we raise the count, finding common points, while more and more segments starting and adding to each other like a Union..; going from right to left we do the same, but raise the counter if this direction contains more common points than previous direction... ", but it is quite obsure why this "directions competition" brings the right result...Not easy...
$endgroup$
– Vladimir Nabokov
Mar 20 at 8:15
$begingroup$
@VladimirNabokov, the main idea is that in the second phase, the count variable at a given point equals the number of segments intersecting that point. By the way, there is only one traversal, from left to right. I think it will be easy to understand the algorithm if you first understand why it works for the cases of one segment only, and two segments only.
$endgroup$
– Vincenzo
Mar 20 at 10:19
|
show 1 more comment
$begingroup$
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)
Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:
(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)
Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.
(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1
This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.
answered Mar 19 at 10:12
VincenzoVincenzo
1,9171614
$endgroup$
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)
Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:
(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)
Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.
(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1
This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.
answered Mar 19 at 10:12
VincenzoVincenzo
1,9171614
edited Mar 19 at 13:56
answered Mar 19 at 10:12
VincenzoVincenzo
1,9171614
answered Mar 19 at 10:12
VincenzoVincenzo
1,9171614
answered Mar 19 at 10:12
VincenzoVincenzo
1,9171614
1,9171614
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
Mar 19 at 11:29
1
$begingroup$
As endpoints are bounded integers, you even can skip the sort phase and just count the number of "in" and "out" on every position (4 K integers).
$endgroup$
– Vince
Mar 19 at 13:44
$begingroup$
@Vince you have to account for closed/open interval ends. That's what the 4 in 4 K is, I guess?
$endgroup$
– John Dvorak
Mar 19 at 17:27
$begingroup$
Thanks. My problem that the answer is looking like a voodoo. It does resolve the problem, but there is no explanation that could explain it properly. Tentatively, I explain it to myself by following: "going from left to right, we raise the count, finding common points, while more and more segments starting and adding to each other like a Union..; going from right to left we do the same, but raise the counter if this direction contains more common points than previous direction... ", but it is quite obsure why this "directions competition" brings the right result...Not easy...
$endgroup$
– Vladimir Nabokov
Mar 20 at 8:15
$begingroup$
@VladimirNabokov, the main idea is that in the second phase, the count variable at a given point equals the number of segments intersecting that point. By the way, there is only one traversal, from left to right. I think it will be easy to understand the algorithm if you first understand why it works for the cases of one segment only, and two segments only.
$endgroup$
– Vincenzo
Mar 20 at 10:19
|
show 1 more comment
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
Mar 19 at 11:29
1
$begingroup$
As endpoints are bounded integers, you even can skip the sort phase and just count the number of "in" and "out" on every position (4 K integers).
$endgroup$
– Vince
Mar 19 at 13:44
$begingroup$
@Vince you have to account for closed/open interval ends. That's what the 4 in 4 K is, I guess?
$endgroup$
– John Dvorak
Mar 19 at 17:27
$begingroup$
Thanks. My problem that the answer is looking like a voodoo. It does resolve the problem, but there is no explanation that could explain it properly. Tentatively, I explain it to myself by following: "going from left to right, we raise the count, finding common points, while more and more segments starting and adding to each other like a Union..; going from right to left we do the same, but raise the counter if this direction contains more common points than previous direction... ", but it is quite obsure why this "directions competition" brings the right result...Not easy...
$endgroup$
– Vladimir Nabokov
Mar 20 at 8:15
$begingroup$
@VladimirNabokov, the main idea is that in the second phase, the count variable at a given point equals the number of segments intersecting that point. By the way, there is only one traversal, from left to right. I think it will be easy to understand the algorithm if you first understand why it works for the cases of one segment only, and two segments only.
$endgroup$
– Vincenzo
Mar 20 at 10:19
1
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
Mar 19 at 11:29
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
Mar 19 at 11:29
1
1
$begingroup$
As endpoints are bounded integers, you even can skip the sort phase and just count the number of "in" and "out" on every position (4 K integers).
$endgroup$
– Vince
Mar 19 at 13:44
$begingroup$
As endpoints are bounded integers, you even can skip the sort phase and just count the number of "in" and "out" on every position (4 K integers).
$endgroup$
– Vince
Mar 19 at 13:44
$begingroup$
@Vince you have to account for closed/open interval ends. That's what the 4 in 4 K is, I guess?
$endgroup$
– John Dvorak
Mar 19 at 17:27
$begingroup$
@Vince you have to account for closed/open interval ends. That's what the 4 in 4 K is, I guess?
$endgroup$
– John Dvorak
Mar 19 at 17:27
$begingroup$
Thanks. My problem that the answer is looking like a voodoo. It does resolve the problem, but there is no explanation that could explain it properly. Tentatively, I explain it to myself by following: "going from left to right, we raise the count, finding common points, while more and more segments starting and adding to each other like a Union..; going from right to left we do the same, but raise the counter if this direction contains more common points than previous direction... ", but it is quite obsure why this "directions competition" brings the right result...Not easy...
$endgroup$
– Vladimir Nabokov
Mar 20 at 8:15
$begingroup$
Thanks. My problem that the answer is looking like a voodoo. It does resolve the problem, but there is no explanation that could explain it properly. Tentatively, I explain it to myself by following: "going from left to right, we raise the count, finding common points, while more and more segments starting and adding to each other like a Union..; going from right to left we do the same, but raise the counter if this direction contains more common points than previous direction... ", but it is quite obsure why this "directions competition" brings the right result...Not easy...
$endgroup$
– Vladimir Nabokov
Mar 20 at 8:15
$begingroup$
@VladimirNabokov, the main idea is that in the second phase, the count variable at a given point equals the number of segments intersecting that point. By the way, there is only one traversal, from left to right. I think it will be easy to understand the algorithm if you first understand why it works for the cases of one segment only, and two segments only.
$endgroup$
– Vincenzo
Mar 20 at 10:19
$begingroup$
@VladimirNabokov, the main idea is that in the second phase, the count variable at a given point equals the number of segments intersecting that point. By the way, there is only one traversal, from left to right. I think it will be easy to understand the algorithm if you first understand why it works for the cases of one segment only, and two segments only.
$endgroup$
– Vincenzo
Mar 20 at 10:19
|
show 1 more comment
$begingroup$
Let's build an array of size 2*k+1 all initialized with 0. For each segment of the form [L, R], we will add 1 at Lth index and subtract 1 from R+1th index.
Note : We add K to every values to shift the range from -K to +K to 0 to 2*K.
Now to obtain the result, we will perform a prefix sum.
array[i] = array[i-1] + array[i], where 1 <= i <= 2*K ( assuming 0-based indexing)
Let i be the index with maximum value. Then answer will be i-K.
Let us solve the asked example :
Let K = 5 and segments are [-2, 3], [1, 5] and [-3, 1]. Then after adding K the segments become
[3, 8], [6, 10] and [2, 6].
On performing the +1 and -1 updates our array will be
[0, 0, 1, 1, 0, 0, 1, -1, 0, -1, 0, -1].
Prefix sum will result into
[0, 0, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0].
Hence the index with max value is 6 and hence answer will be 6 - 5 = 1.
Time complexity of above approach will be O(max(N, K)).
answered Mar 20 at 7:31
Shiv ShankarShiv Shankar
362
$endgroup$
add a comment |
$begingroup$
Let's build an array of size 2*k+1 all initialized with 0. For each segment of the form [L, R], we will add 1 at Lth index and subtract 1 from R+1th index.
Note : We add K to every values to shift the range from -K to +K to 0 to 2*K.
Now to obtain the result, we will perform a prefix sum.
array[i] = array[i-1] + array[i], where 1 <= i <= 2*K ( assuming 0-based indexing)
Let i be the index with maximum value. Then answer will be i-K.
Let us solve the asked example :
Let K = 5 and segments are [-2, 3], [1, 5] and [-3, 1]. Then after adding K the segments become
[3, 8], [6, 10] and [2, 6].
On performing the +1 and -1 updates our array will be
[0, 0, 1, 1, 0, 0, 1, -1, 0, -1, 0, -1].
Prefix sum will result into
[0, 0, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0].
Hence the index with max value is 6 and hence answer will be 6 - 5 = 1.
Time complexity of above approach will be O(max(N, K)).
answered Mar 20 at 7:31
Shiv ShankarShiv Shankar
362
$endgroup$
add a comment |
$begingroup$
Let's build an array of size 2*k+1 all initialized with 0. For each segment of the form [L, R], we will add 1 at Lth index and subtract 1 from R+1th index.
Note : We add K to every values to shift the range from -K to +K to 0 to 2*K.
Now to obtain the result, we will perform a prefix sum.
array[i] = array[i-1] + array[i], where 1 <= i <= 2*K ( assuming 0-based indexing)
Let i be the index with maximum value. Then answer will be i-K.
Let us solve the asked example :
Let K = 5 and segments are [-2, 3], [1, 5] and [-3, 1]. Then after adding K the segments become
[3, 8], [6, 10] and [2, 6].
On performing the +1 and -1 updates our array will be
[0, 0, 1, 1, 0, 0, 1, -1, 0, -1, 0, -1].
Prefix sum will result into
[0, 0, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0].
Hence the index with max value is 6 and hence answer will be 6 - 5 = 1.
Time complexity of above approach will be O(max(N, K)).
answered Mar 20 at 7:31
Shiv ShankarShiv Shankar
362
$endgroup$
Let's build an array of size 2*k+1 all initialized with 0. For each segment of the form [L, R], we will add 1 at Lth index and subtract 1 from R+1th index.
Note : We add K to every values to shift the range from -K to +K to 0 to 2*K.
Now to obtain the result, we will perform a prefix sum.
array[i] = array[i-1] + array[i], where 1 <= i <= 2*K ( assuming 0-based indexing)
Let i be the index with maximum value. Then answer will be i-K.
Let us solve the asked example :
Let K = 5 and segments are [-2, 3], [1, 5] and [-3, 1]. Then after adding K the segments become
[3, 8], [6, 10] and [2, 6].
On performing the +1 and -1 updates our array will be
[0, 0, 1, 1, 0, 0, 1, -1, 0, -1, 0, -1].
Prefix sum will result into
[0, 0, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0].
Hence the index with max value is 6 and hence answer will be 6 - 5 = 1.
Time complexity of above approach will be O(max(N, K)).
answered Mar 20 at 7:31
Shiv ShankarShiv Shankar
362
answered Mar 20 at 7:31
Shiv ShankarShiv Shankar
362
answered Mar 20 at 7:31
Shiv ShankarShiv Shankar
362
answered Mar 20 at 7:31
Shiv ShankarShiv Shankar
362
362
add a comment |
add a comment |
Vladimir Nabokov is a new contributor. Be nice, and check out our Code of Conduct.
Vladimir Nabokov is a new contributor. Be nice, and check out our Code of Conduct.
Vladimir Nabokov is a new contributor. Be nice, and check out our Code of Conduct.
Vladimir Nabokov is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2fcs.stackexchange.com%2fquestions%2f105773%2ffind-a-point-shared-by-maximum-segments%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
