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 yesterday
xskxzr
3,93121032
asked yesterday
Vladimir NabokovVladimir Nabokov
1361
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 yesterday
xskxzr
3,93121032
asked yesterday
Vladimir NabokovVladimir Nabokov
1361
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 yesterday
xskxzr
3,93121032
asked yesterday
Vladimir NabokovVladimir Nabokov
1361
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 yesterday
xskxzr
3,93121032
asked yesterday
Vladimir NabokovVladimir Nabokov
1361
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 yesterday
xskxzr
3,93121032
asked yesterday
Vladimir NabokovVladimir Nabokov
1361
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 yesterday
xskxzr
3,93121032
edited yesterday
xskxzr
3,93121032
edited yesterday
xskxzr
3,93121032
3,93121032
asked yesterday
Vladimir NabokovVladimir Nabokov
1361
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 yesterday
Vladimir NabokovVladimir Nabokov
1361
asked yesterday
Vladimir NabokovVladimir Nabokov
1361
1361
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 yesterday
VincenzoVincenzo
1,8521514
$endgroup$
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
yesterday
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
yesterday
$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
yesterday
$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
12 hours ago
$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
10 hours ago
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 13 hours ago
Shiv ShankarShiv Shankar
262
$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 yesterday
VincenzoVincenzo
1,8521514
$endgroup$
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
yesterday
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
yesterday
$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
yesterday
$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
12 hours ago
$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
10 hours ago
add a 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 yesterday
VincenzoVincenzo
1,8521514
$endgroup$
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
yesterday
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
yesterday
$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
yesterday
$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
12 hours ago
$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
10 hours ago
add a 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 yesterday
VincenzoVincenzo
1,8521514
$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 yesterday
VincenzoVincenzo
1,8521514
edited yesterday
answered yesterday
VincenzoVincenzo
1,8521514
answered yesterday
VincenzoVincenzo
1,8521514
answered yesterday
VincenzoVincenzo
1,8521514
1,8521514
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
yesterday
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
yesterday
$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
yesterday
$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
12 hours ago
$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
10 hours ago
add a comment |
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
yesterday
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
yesterday
$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
yesterday
$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
12 hours ago
$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
10 hours ago
1
1
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
yesterday
$begingroup$
There is an alternative solution using segment trees. But the asymptotic cost is the same.
$endgroup$
– Vincenzo
yesterday
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
yesterday
$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
yesterday
$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
yesterday
$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
yesterday
$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
12 hours ago
$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
12 hours ago
$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
10 hours ago
$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
10 hours ago
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 13 hours ago
Shiv ShankarShiv Shankar
262
$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 13 hours ago
Shiv ShankarShiv Shankar
262
$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 13 hours ago
Shiv ShankarShiv Shankar
262
$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 13 hours ago
Shiv ShankarShiv Shankar
262
answered 13 hours ago
Shiv ShankarShiv Shankar
262
answered 13 hours ago
Shiv ShankarShiv Shankar
262
answered 13 hours ago
Shiv ShankarShiv Shankar
262
262
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
