1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ "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? $\endgroup$
    – John L.
    Commented Feb 1, 2019 at 7:08
  • $\begingroup$ @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 $\endgroup$
    – user94342
    Commented Feb 1, 2019 at 8:21
  • $\begingroup$ 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. $\endgroup$
    – j_random_hacker
    Commented Feb 1, 2019 at 15:05
  • $\begingroup$ 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! $\endgroup$
    – Raphael
    Commented Feb 1, 2019 at 15:19

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Feb 1, 2019 at 14:39
  • $\begingroup$ @Apass.Jack: It answers the question "I have to find an event that conflict with maximum number of other events". If the OP wants something different -- for example if they want to know whether a given event conflicts with any other events -- they need to update their question. $\endgroup$
    – j_random_hacker
    Commented Feb 1, 2019 at 15:06
  • $\begingroup$ Yes, your answer does provide a solution to that task. However, as far as I checked, people here generally consider statement with question marks as questions, although it is not far-fetched at all to consider that task as a question such as "can you find that event?". By the way, did you notice there is a boldface "Question" at the end of the post? Once again, nice algorithm. $\endgroup$
    – John L.
    Commented Feb 1, 2019 at 15:14
  • $\begingroup$ Upvoted, anyway. $\endgroup$
    – John L.
    Commented Nov 18, 2021 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.