# Finding Conflict algorithm doubt

Let $$e_1,e_2,\cdots,e_n$$ are some events are given by their starting time and ending time.

I have to find an event that conflict with maximum number of other events.

Conflicts means interval overlaps

The idea is as follows: Sort events according to their starting times and then for each event check whether it conflict with other evenets or not. The first step seems to me doable in $$\mathcal{O}(n \log n)$$ time, but second step i.e. to find the number of events with which it conflicts is seems to $$\mathcal{O}(n)$$ Can we do it in $$\mathcal{O}(\log n)$$ time?

Question : Is it possible to do the second step as mentioned above in $$\mathcal{O}(\log n)$$ time?

• "the second step as mentioned above in $\mathcal O(\log 𝑛)$ time". By "the second step", do you mean "for each event check whether it conflict with other events or not" or just "check whether it conflict with other events or not" for one event? In fact, either meaning would lead to a negative answer, I believe. However, are you actually asking is it possible to "for each event check ..." in $\mathcal O(n\log 𝑛)$ time or even in $\mathcal O(𝑛)$ time? – John L. Feb 1 '19 at 7:08
• @Apass.Jack for a one fixed event, is it possible to find all the events with which it conflicts in $\mathcal{O}(\log n)$ time – user94342 Feb 1 '19 at 8:21
• If you want to find all events that conflict with a given event, change your question to reflect that. As it stands, you are (literally) asking for finding an event that conflicts with a maximum number of other events, which my algorithm solves in $O(n \log n)$ time. – j_random_hacker Feb 1 '19 at 15:05
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Feb 1 '19 at 15:19

Take all $$2n$$ starting and ending times and sort them, then walk through the list in sorted order, increasing a counter at each "starting" time, and decreasing the counter at each "ending" time. On every counter increase, check whether this is the highest the counter has gone so far, and if so update the best-so-far event.
• Nice algorithm. I am afraid this answer does not answer the main question, though. You may want to point out/analyze it is probably pointless to search for a way to do the second step in $\mathcal O(\log n)$ time. – John L. Feb 1 '19 at 14:39