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.

Postmark Image

Speedy emails, satisfied customers

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

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more