I came across this question...
Hope someone can shed some light on how I can tackle this as I learn..
I'm new into algorithms.
A famous ride-sharing company Ubunifu has recently created a new “shared-bus” service in view of the COViD-19 pandemic. The bus serves a path of k kilometres, indexed by [0, k]. The main differences between this service and the traditional bus services are:
(a) All the passengers board the bus at point 0.
(b) Passenger i specifies a range from starting point s and terminal point t as
[si , ti ](0 ≤ si ≤ ti ≤ k).
The passenger is satisfied as long as the bus stops at some location between si and ti (including the boundary). There are no fixed bus stops. Instead, the stops will be decided after gathering the user information s and t. As an IT officer at Ubunifu, you need to solve the following problem: given the number of passengers n, and each passenger’s preference [si, ti ], design an algorithm that finds the smallest number of stops in order to satisfy all passengers and analyze its running time.
Your algorithm should run in O(n log n) time.
Top comments (1)
Lets see if Asymptotic analysis will solve it