DEV Community

Billy Okeyo
Billy Okeyo

Posted on

1

Algorithms

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).
Enter fullscreen mode Exit fullscreen mode

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.

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (1)

Collapse
 
olalatheexpert profile image
OlalaTheExpert

Lets see if Asymptotic analysis will solve it

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

👥 Ideal for solo developers, teams, and cross-company projects

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay