Assignment - Aston Martin rental requests

Hello everybody. I got stuck on this assignment and I really don't know what to do. The assignment is:

.

_____________________________________________________________________________________

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.

An easy example input could be:

list = [...
 10 20;
  9 15;
 16 17; 
21 100;
];

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]

_____________________________________________________________________________________

Any idea? Thanks in advance!

[James Tursa]

What have you done so far? What specific problems are you having with your code?

[Matteo Tafuro]

I tried a bit of everything but I really can't figure out how to do it. I was (partially) able to do it for one single customer of the list:

clear;
close all;
clc;

list = [...
10 20;
9 15;
16 17;
21 100;
];

 %%Make arrays with the days intervals

 n_customers = size(list,1);
 days = zeros(n_customers,length(list(:,1):list(:,2)));

 for i = 1 : n_customers
    days(i,1:(length(list(i,1):list(i,2)))) =  [list(i,1):list(i,2)];
 end

 days(days==0) = nan; % Delete all zero

 %%FOR A SINGLE CUSTOMER
 counter = 2
 customer = 4
 taken_days = days(customer,:)

 for i = 1 : n_customers
        intersections{i}=intersect(days(customer,:),days(i,:))

        combinations(1) = customer
        if isempty(intersections{i}) == 1
            combinations(counter) = i
            counter = counter + 1
        end    
 end

It works for customers 1,2 and 3, but if I put customer = 4 then it does not.

Anyways, this is not even close to what I'm supposed to achieve. I don't know how to proceed.

[Matteo Tafuro]

So with this code, I get the following output:

combinations =

     1     4

So the first 1 can be combined with the 4th one without overlapping. Similarly, with customer = 2:

combinations =

     2     3     4

With customer = 3:

combinations =

     3     2     4

But then, with customer = 4,

combinations =

     4     1     2     3

And this is not correct, because the range of days are now overlapping.

[James Tursa]

What class is this for? An optimization course, or a programming course? Code to get a general solution for this isn't going to be trivial, particularly if there are a lot of customers. How many customers could you have? It there are not too many, a brute force method might suffice.

[Matteo Tafuro]

It's a programming course. They also gave me another list to try my code with, so I think that will be the maximum number of customers that they will use:

list = [...
    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;
    153 181;
    197 216;
    283 307;
    194 199;
    82 109; 
    10 25;
    60 90;
    256 271;
    172 173; ];

[James Tursa]

Has your teacher given you any clue as to what is expected for the optimization code? Or are you just supposed to come up with something entirely on your own? A brute force method outline would be:

See if you can select everybody. 
  If so, then you are done.
If not, then try all combinations with 1 person missing. 
  If any of these work, then you are done.
If not, then try all combinations with 2 people missing.
  If any of these work, then you are done.
  :
 etc

But this could take a very long time if the list is too big. That is why I asked if the teacher has given you instruction about what method is expected.

[Image Analyst]

Here's a photo of me driving mine.

Since it costs $22.6 million, I don't let anyone drive it.

[James Tursa]

IA's code:

customers = [];
days = [];

[Matteo Tafuro]

Nope James Tursa, no clue. I have to come up with something myself