Ygtjki

Why does a 97 / 92 key piano exist by Bosendorfer?

Is this saw blade faulty?

Should I warn a new PhD Student?

Did I make a mistake by ccing email to boss to others?

Friend wants my recommendation but I don't want to give it to him

Why is participating in the European Parliamentary elections used as a threat?

Reason why a kingside attack is not justified

Should I be concerned about student access to a test bank?

Weird lines in Microsoft Word

Not hide and seek

Error in master's thesis, I do not know what to do

How to test the sharpness of a knife?

What is the meaning of "You've never met a graph you didn't like?"

Extract substring according to regexp with sed or grep

How to get directions in deep space?

Magnifying glass in hyperbolic space

Writing in a Christian voice

Is there any common country to visit for persons holding UK and Schengen visas?

Started in 1987 vs. Starting in 1987

How to split IPA spelling into syllables

Turning a hard to access nut?

A seasonal riddle

Reasons for having MCU pin-states default to pull-up/down out of reset

What is this high flying aircraft over Pennsylvania?

Find a point shared by maximum segments

How to approach Vertical Sticks challengeLower-bound complexities for finding common elements between two unsorted arraysEfficient algorithms for vertical visibility problemsolving a number theoretical problemGiven an amount of sets with numbers, find a set of numbers not including any of the givenHow can I prove algorithm correctness?Find a Minimal Set of Combined TuplesFor given set of integers, find and count the pairs with maximum value of bitwise orHow to define the partial or total order of the segments to be inserted in a “sweep-line status” data structure?Maximum product of contiguous subsequence over $mathbbR$

7

1

$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

share|cite|improve this question

edited 19 hours ago

xskxzr

3,92121032

asked 21 hours ago

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 | 

7

1

$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

share|cite|improve this question

edited 19 hours ago

xskxzr

3,92121032

asked 21 hours ago

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

share|cite|improve this question

edited 19 hours ago

xskxzr

3,92121032

asked 21 hours ago

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$

Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]

Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]

share|cite|improve this question

edited 19 hours ago

xskxzr

3,92121032

asked 21 hours ago

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.

share|cite|improve this question

edited 19 hours ago

xskxzr

3,92121032

asked 21 hours ago

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 19 hours ago

xskxzr

3,92121032

edited 19 hours ago

xskxzr

3,92121032

asked 21 hours ago

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 21 hours ago

Vladimir NabokovVladimir Nabokov

1361

1 Answer
1

active

oldest

votes

11

$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.

share|cite|improve this answer

edited 16 hours ago

answered 20 hours ago

VincenzoVincenzo

1,8521514

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There is an alternative solution using segment trees. But the asymptotic cost is the same.
  $endgroup$
  – Vincenzo
  19 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  16 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  13 hours ago
  

  
  
  
  

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.

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

11

$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.

share|cite|improve this answer

edited 16 hours ago

answered 20 hours ago

VincenzoVincenzo

1,8521514

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There is an alternative solution using segment trees. But the asymptotic cost is the same.
  $endgroup$
  – Vincenzo
  19 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  16 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  13 hours ago
  

  
  
  
  

add a comment | 

11

$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.

share|cite|improve this answer

edited 16 hours ago

answered 20 hours ago

VincenzoVincenzo

1,8521514

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There is an alternative solution using segment trees. But the asymptotic cost is the same.
  $endgroup$
  – Vincenzo
  19 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  16 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  13 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.

share|cite|improve this answer

edited 16 hours ago

answered 20 hours ago

VincenzoVincenzo

1,8521514

$endgroup$

Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)

(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)

(-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

share|cite|improve this answer

edited 16 hours ago

answered 20 hours ago

VincenzoVincenzo

1,8521514

answered 20 hours ago

VincenzoVincenzo

1,8521514

answered 20 hours ago

VincenzoVincenzo

1,8521514