2
$\begingroup$

Given two $n$-number arrays $a_1, a_2, \ldots,a_n \in [0,1] $ and $b_1, b_2, \ldots,b_n \in [0,1] $. We would like to find the real number $x^{*} \in (0,1)$ s.t:

$x^{*} =\arg\max_{x} \sum_{i=1}^n \mathrm{sgn} \big( (a_i-x) (b_i -x)\big) $

Where $\mathrm{sgn} = 1 $ if $x \geq 0$ and $\mathrm{sgn} = -1$ if $x < 0$

This question raised from my research work. I am looking for an efficient way to determine value of $x$.

$\endgroup$
2
$\begingroup$

WLOG, let $a_i < b_i$. Then $(a_1 - x)(b_i - x) \geq 0$ when $x \leq a_i \vee x \geq b_i$.

Keep a list of intervals $I$. For each $a_i , b_i$ add $(0, a_i]$ and $[b_i, 1)$ to the intervals. Now you just find point $x$ such that it lies within the most intervals in $I$.

$\endgroup$
  • $\begingroup$ In other words, you sort $a_1,b_1,\ldots,a_n,b_n$, and then scan the result from left to right, keeping track of the number of intervals covering at each "event" point. $\endgroup$ – Yuval Filmus Jul 2 '18 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.