-3

I've had this Interview question and I would like to know how to solve that: I have tried to find an answer for that on Google and here but no success "Given a long list of events with start point and end point, find the time where intersection was highest "

not allowed to use any complex data structure

thank you

yuria
  • 541
  • 2
  • 7
  • 22
  • have a look at http://stackoverflow.com/questions/17466218/what-are-the-differences-between-segment-trees-interval-trees-binary-indexed-t – Alex Apr 29 '15 at 15:39

1 Answers1

1

Sort the times into ascending order and then run along them, incrementing a counter at a start and decrementing it at an end. The time with highest intersection should be the time when the counter reached its highest value.

mcdowella
  • 19,301
  • 2
  • 19
  • 25