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 edited Sep 1 '14 at 10:51 Raphael♦ 66.4k2626 gold badges146146 silver badges327327 bronze badges First sort both $$x1$$ and $$x2$$ coordinates of the lines in two seperate arrays $$A$$ and $$B$$. $$O(m)$$ We also maintain an auxilary bit array size $$n$$ to keep track of the active segments. Start sweeping from the left to right: for $$(i=0,i { ..if $$\exists x1=i$$ with $$y$$ value $$c$$ $$O(1)$$ ..{ ....find($$max$$$$\max$$) ....store($$max$$$$\max$$) $$O(1)$$ ..} ..if $$\exists x2=i$$ with $$y$$ value $$c$$ $$O(1)$$ ..{ ....find($$max$$$$\max$$) ....store($$max$$$$\max$$) $$O(1)$$ ..} } 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... First sort both $$x1$$ and $$x2$$ coordinates of the lines in two seperate arrays $$A$$ and $$B$$. $$O(m)$$ We also maintain an auxilary bit array size $$n$$ to keep track of the active segments. Start sweeping from the left to right: for $$(i=0,i { ..if $$\exists x1=i$$ with $$y$$ value $$c$$ $$O(1)$$ ..{ ....find($$max$$) ....store($$max$$) $$O(1)$$ ..} ..if $$\exists x2=i$$ with $$y$$ value $$c$$ $$O(1)$$ ..{ ....find($$max$$) ....store($$max$$) $$O(1)$$ ..} } 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... First sort both $$x1$$ and $$x2$$ coordinates of the lines in two seperate arrays $$A$$ and $$B$$. $$O(m)$$ We also maintain an auxilary bit array size $$n$$ to keep track of the active segments. Start sweeping from the left to right: for $$(i=0,i { ..if $$\exists x1=i$$ with $$y$$ value $$c$$ $$O(1)$$ ..{ ....find($$\max$$) ....store($$\max$$) $$O(1)$$ ..} ..if $$\exists x2=i$$ with $$y$$ value $$c$$ $$O(1)$$ ..{ ....find($$\max$$) ....store($$\max$$) $$O(1)$$ ..} } 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 answered Sep 1 '14 at 6:27 invalid_id 12377 bronze badges First sort both $$x1$$ and $$x2$$ coordinates of the lines in two seperate arrays $$A$$ and $$B$$. $$O(m)$$ We also maintain an auxilary bit array size $$n$$ to keep track of the active segments. Start sweeping from the left to right: for $$(i=0,i { ..if $$\exists x1=i$$ with $$y$$ value $$c$$ $$O(1)$$ ..{ ....find($$max$$) ....store($$max$$) $$O(1)$$ ..} ..if $$\exists x2=i$$ with $$y$$ value $$c$$ $$O(1)$$ ..{ ....find($$max$$) ....store($$max$$) $$O(1)$$ ..} } 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...