Today I was looking at problems related to linked lists. They tend to be asked quite a lot in interviews but some of them look artificial with their complexity arising from linked lists being a poor data structure for the problem (e.g., median of a sorted linked list). The problem of the day for today is Detecting cycle in a linked list: *Given a linked list, return the node where the cycle begins or null if there is no cycle.* For example, in the image below, 4 should be returned.

# Tag Archives: proof

# Scheduling to minimize lateness

The problem can be stated as follows :

*“Given a set of n jobs all of which must be scheduled on a single resource such that all jobs arrive at time s and each job has a deadline d _{i} and a length t_{i}, minimize the maximum lateness of the resulting schedule.”*

We need to assign a start time s_{i} to each job i. Jobs are allowed to be late i.e., a job i may finish at time f_{i} = s_{i} + t_{i} > d_{i}. If job i is late, its lateness is defined to be l_{i} = f_{i} – d_{i}. Otherwise, l_{i} = 0. So the objective is to find a schedule that minimizes the maximum lateness, L = max_{i} l_{i}.

# Interval Partitioning Problem

The interval partitioning problem is described as follows:

*Given a set {1, 2, …, n} of n requests, where i ^{th} request starts at time s(i) and finishes at time f(i), find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time. Two requests i and j can conflict in one of two ways:*

- s(i) <= s(j) and f(i) > s(j)
- s(j) <= s(i) and f(j) > s(i)

**Example:** Given 3 requests with s(1) = 1, f(1) = 3, s(2) = 2, f(2) = 4, s(3) = 3, f(3) = 5, at least 2 resources are needed to satisfy all requests. A valid assignment of requests to resources is {1, 3} and {2}.

# Interval Scheduling Problem

The interval scheduling problem is described as follows:

*Given a set {1, 2, …, n} of n requests, where i ^{th} request starts at time s(i) and finishes at time f(i), find a maximum-size subset of compatible requests. Two requests i and j are compatible if they do not overlap i.e., either f(i) <= s(j) or f(j) <= s(i).*

**Example:** Given 3 requests with s(1) = 1, f(1) = 3, s(2) = 2, f(2) = 4, s(3) = 3, f(3) = 5, the maximum-size subset of compatible requests is {1, 3}.