Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
2 added 5 characters in body
source | link
  1. First sort both $x1$ and $x2$ coordinates of the lines in two seperate arrays $A$ and $B$. $O(m)$
  2. We also maintain an auxilary bit array size $n$ to keep track of the active segments.
  3. Start sweeping from the left to right:
  4. for $(i=0,i<n,i++)$
  5. {
  6. ..if $\exists x1=i$ with $y$ value $c$ $O(1)$
  7. ..{
  8. ....find($max$$\max$)
  9. ....store($max$$\max$) $O(1)$
  10. ..}
  11. ..if $\exists x2=i$ with $y$ value $c$ $O(1)$
  12. ..{
  13. ....find($max$$\max$)
  14. ....store($max$$\max$) $O(1)$
  15. ..}
  16. }

find($max$$\max$) can be implemented using an bit array with $n$ bits. Now whenever we remove or add an element to $L$ we can update this integer by setting a bit to true or false respectively. Now you have two options depending on the programming language used and the assumption $n$ is relatively small i.e. smaller than $long long int$ which is at least 64 bits or a fixed amount of these integers:

  • Get the least significant bit in constant time is supported by some hardware and gcc.
  • By converting $L$ to an integer $O(1)$ you will get the maximum (not directly but you can derive it).

I know this is quite a hack because it assumes a maximum value for $n$ and hence $n$ can be seen as a constant then...

  1. First sort both $x1$ and $x2$ coordinates of the lines in two seperate arrays $A$ and $B$. $O(m)$
  2. We also maintain an auxilary bit array size $n$ to keep track of the active segments.
  3. Start sweeping from the left to right:
  4. for $(i=0,i<n,i++)$
  5. {
  6. ..if $\exists x1=i$ with $y$ value $c$ $O(1)$
  7. ..{
  8. ....find($max$)
  9. ....store($max$) $O(1)$
  10. ..}
  11. ..if $\exists x2=i$ with $y$ value $c$ $O(1)$
  12. ..{
  13. ....find($max$)
  14. ....store($max$) $O(1)$
  15. ..}
  16. }

find($max$) can be implemented using an bit array with $n$ bits. Now whenever we remove or add an element to $L$ we can update this integer by setting a bit to true or false respectively. Now you have two options depending on the programming language used and the assumption $n$ is relatively small i.e. smaller than $long long int$ which is at least 64 bits or a fixed amount of these integers:

  • Get the least significant bit in constant time is supported by some hardware and gcc.
  • By converting $L$ to an integer $O(1)$ you will get the maximum (not directly but you can derive it).

I know this is quite a hack because it assumes a maximum value for $n$ and hence $n$ can be seen as a constant then...

  1. First sort both $x1$ and $x2$ coordinates of the lines in two seperate arrays $A$ and $B$. $O(m)$
  2. We also maintain an auxilary bit array size $n$ to keep track of the active segments.
  3. Start sweeping from the left to right:
  4. for $(i=0,i<n,i++)$
  5. {
  6. ..if $\exists x1=i$ with $y$ value $c$ $O(1)$
  7. ..{
  8. ....find($\max$)
  9. ....store($\max$) $O(1)$
  10. ..}
  11. ..if $\exists x2=i$ with $y$ value $c$ $O(1)$
  12. ..{
  13. ....find($\max$)
  14. ....store($\max$) $O(1)$
  15. ..}
  16. }

find($\max$) can be implemented using an bit array with $n$ bits. Now whenever we remove or add an element to $L$ we can update this integer by setting a bit to true or false respectively. Now you have two options depending on the programming language used and the assumption $n$ is relatively small i.e. smaller than $long long int$ which is at least 64 bits or a fixed amount of these integers:

  • Get the least significant bit in constant time is supported by some hardware and gcc.
  • By converting $L$ to an integer $O(1)$ you will get the maximum (not directly but you can derive it).

I know this is quite a hack because it assumes a maximum value for $n$ and hence $n$ can be seen as a constant then...

1
source | link

  1. First sort both $x1$ and $x2$ coordinates of the lines in two seperate arrays $A$ and $B$. $O(m)$
  2. We also maintain an auxilary bit array size $n$ to keep track of the active segments.
  3. Start sweeping from the left to right:
  4. for $(i=0,i<n,i++)$
  5. {
  6. ..if $\exists x1=i$ with $y$ value $c$ $O(1)$
  7. ..{
  8. ....find($max$)
  9. ....store($max$) $O(1)$
  10. ..}
  11. ..if $\exists x2=i$ with $y$ value $c$ $O(1)$
  12. ..{
  13. ....find($max$)
  14. ....store($max$) $O(1)$
  15. ..}
  16. }

find($max$) can be implemented using an bit array with $n$ bits. Now whenever we remove or add an element to $L$ we can update this integer by setting a bit to true or false respectively. Now you have two options depending on the programming language used and the assumption $n$ is relatively small i.e. smaller than $long long int$ which is at least 64 bits or a fixed amount of these integers:

  • Get the least significant bit in constant time is supported by some hardware and gcc.
  • By converting $L$ to an integer $O(1)$ you will get the maximum (not directly but you can derive it).

I know this is quite a hack because it assumes a maximum value for $n$ and hence $n$ can be seen as a constant then...