CODEWITHSUNDEEP
matlab
Kcinnay
Kcinnay

Reputation: 13

Creating an optimal selection of overlapping time intervals

A car dealer rents out the rare 1956 Aston Martin DBR1 (of which Aston Martin only ever made 5). Since there are so many rental requests, the dealer decides to place bookings for an entire year in advance. He collects the requests and now needs to figure out which requests to take.

Make a script that selects the rental requests such that greatest number of individual customers can drive in the rare Aston Martin. The input of the script is a matrix of days of the year, each row representing the starting and ending days of the request. The output should be the indices of the customers and their day ranges. It is encouraged to plan your code first and write your own functions. At the top of the script, add a comment block with a description of how your code works.

Example of a list with these time intervals: list = [10 20; 9 15; 16 17; 21 100;];

(It should also work for a list with 100 time intervals)

We could select customers 1 and 4, but then 2 and 3 are impossible, resulting in two happy customers. Alternatively we could select requests 2, 3 and 4. Hence three happy customers is the optimum here.

The output would be: customers = [2, 3, 4], days = [9, 15; 16, 17; 21, 100]

All I can think of is checking if intervals intersect, but I have no clue how to make an overall optimal selection.

Upvotes: 1

Views: 128

Answers (2)

Roberto
Roberto

Reputation: 1097

Wanted to expand/correct a little bit on the acvepted answer.

  1. You should start by sorting by the start date.
  2. Then accept the very last customer.
  3. Go through the list descending from there and accept all request that do not overlap with the already accepted ones.

That's the optimal solution.

Upvotes: 0

Dmitry Reutov
Dmitry Reutov

Reputation: 3032

My idea: 1) Sort them by start date

2) Make an array of intersections for each one

3) Start to reject from the ones which has the biggest intersection array, removing rejected item from arrays of intersected units

4) Repeat point 3 until only units with empty arrays will remain

In your example we will get data

10 20 [9 15, 16 17] 
9 15 [10 20]
16 17 [10 20]
21 100 []

so we reject 10 20 as it has 2 intersections, so we will have only items with empty arrays

9 15 []
16 17 []
21 100 []

so the search is finished

code on javascript

const inputData = ' 50 74; 6 34; 147 162; 120 127; 98 127; 120 136; 53 68; 145 166; 95 106; 242 243; 222 250; 204 207; 69 79; 183 187; 198 201; 184 199; 223 245; 264 291; 100 121; 61 61; 232 247'

// convert string to array of objects
const orders = inputData.split(';')
  .map((v, index) => (
    {
      id: index,
      start: Number(v.split(' ')[1]),
      end: Number(v.split(' ')[2]),
      intersections: []
    }
  ))

// sort them by start value
orders.sort((a, b) => a.start - b.start)

// find intersection for each one and add them to intersection array
orders.forEach((item, index) => {
  for (let i = index + 1; i < orders.length; i++) {
    if (orders[i].start <= item.end) {
      item.intersections.push(orders[i])
      orders[i].intersections.push(item)
    } else {
      break
    }
  }
})

// sort by intersections count
orders.sort((a, b) => a.intersections.length - b.intersections.length)

// loop while at least one item still has intersections
while (orders[orders.length - 1].intersections.length > 0) {
  const rejected = orders.pop()
  // remove rejected item from other's intersections
  rejected.intersections.forEach(item => {
    item.intersections = item.intersections.filter(
      item => item.id !== rejected.id
    )
  })
  // sort by intersections count
  orders.sort((a, b) => a.intersections.length - b.intersections.length)
}

// sort by start value
orders.sort((a, b) => a.start - b.start)

// show result
orders.forEach(item => { console.log(item.start + ' - ' + item.end)})

Upvotes: 2

Related Questions