Plz Halp, Need Investors ASAP

Question

Bob has a startup that is developing a product that uses “advanced AI” and “black magic” to automatically code-golf computer programs. Unfortunately, Bob is running out of cash and desperately needs money from investors to keep his company running. Each investor that Bob has contacted wishes to schedule a meeting with a certain start and end time. However, some of meeting times conflict with each other. Bob wishes to meet with as many investors as possible so he can raise the largest amount of money. How many investors can Bob meet with, given that Bob can only meet with one investor at a time?

Input Format

Input is given as an array of pairs (or the equivalent in your chosen language). Each pair p represents one investor, where p[0] is the start time of the investor’s meeting and p[1] is the end time.

For example, in the test case [(0,10),(5,10),(12,13)], there are three investors: one who wants to meet from time 0 to time 10, one who wants to meet from time 5 to time 10, and one who wants to meet from time 12 to time 13. Meetings will always have a positive duration, and a meeting that ends at time k does not conflict with a meeting that starts at time k.

You may use any reasonable I/O method for input.

Test Cases

[(0,10),(5,10),(12,13)] => 2 (investors 1 and 3)

[(10,20),(10,20),(20,30),(15,25)] => 2 (investors 1 and 3)

[(0,3),(1,5),(1,5),(1,5),(4,9),(6,12),(10,15),(13,18),(13,18),(13,18),(17,19)] => 4 (investors 1,5,7 and 11)

[(1,1000),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)] => 6 (every investor except the first)

[(1,2),(101,132),(102,165),(3,9),(10,20),(21,23),(84,87)] => 6 (investors 1,2,4,5,6,7)

Output

Your program should output an integer, the maximum number of investors that Bob can meet with.

Standard loopholes are prohibited. This is code-golf, so the shortest solution in each language wins.

Answer 1

Python 2, 53 52 bytes

Based on xnor's answer.
-1 byte thanks to dingledooper!

f=lambda l,t=0:-min([a<t or~f(l,b)for a,b in l]+[0])

Try it online!

This is a recursive function which takes 2 arguments:

• l: a list of all offered meetings
• t: the time our last meeting ended (initially 0)

The list comprehension iterates over all offered meetings (a, b).
If the meeting starts before our last meeting ended (a<t), a<t or ... evaluates to True, which is basically the same as 1 in Python.
Otherwise f(l,b) is called to see how much more meetings we can fit in if we take the current meeting. The bitwise inverted value of this gets into the list.

If a<t was false for any meeting (a, b) in the comprehension, min returns the smallest of all possible ~f(l,b) values. Then -min(...) returns -~f(l,b)==1+f(l,b) for some meeting.
Otherwise -min(...) is equal to 0.

---

47 bytes if we can assume that the input is not empty:

f=lambda l,t=0:1-min(a<t or-f(l,b)for a,b in l)

Try it online!

Answer 2

Wolfram Language (Mathematica), 49 bytes

If[#==0m,1,1+#0[#.m]]&[m=Boole[#>=#2&~Outer~##]]&

Try it online!

Input [{starting times}, {ending times}].

Finds the least power n such that \$M^n=\mathbf{0}\$, where M is an adjacency matrix representing possible next meetings.

Answer 3

Python 2, 54 bytes

f=lambda l,t=0:max([1+f(l,b)for a,b in l if a>=t]+[0])

Try it online!

Answer 4

J, ^{43 36} 35 bytes

1#@}.(#~0{]>://&.|:@/:{:"1) ::]^:a:

Try it online!

Uses greedy algorithm. Probably more to golf....

orig brute force, 43 bytes

[:>./(2#:@i.@^#)(#*;-:~.@;)@#<@([+i.@-~)/"1

Try it online!

Answer 5

Jelly, 8 bytes

<þ¬æ×Ƭ`L

<þ¬æ×Ƭ`L
<þ        outer product less than
  ¬       negate (outer product greater than or equal to)
   æ×     matrix multiply
     Ƭ`   apply until converged using itself as the left argument
       L  length

Uses the method from the mathematica answer https://codegolf.stackexchange.com/a/224523/95516 go upvote that!

Try it online!

Answer 6

Ruby, 42 bytes

f=->a,b=0{a.map{|c,d|c<b ?0:-~f[a,d]}.max}

Try it online!

This answer is heavily inspired by xnor's python answer.

Answer 7

Charcoal, 22 bytes

Ｗ⌊ΦＥθ⮌ꬋ⊟κ∨⌈υ⁰⊞υ⊟ιＩＬυ

Try it online! Link is to verbose version of code. Explanation:

Ｅθ⮌κ

Reverse each investor meeting, so that the end time comes first and the start time second.

Φ...¬‹⊟κ∨⌈υ⁰

Destructively compare the start times with the latest end time so far, returning just the possible end times of the next meeting.

Ｗ⌊

Take the earliest such time, if any. While it exists:

⊞υ⊟ι

Push that earliest ending time to the predefined empty list.

ＩＬυ

Output the number of meetings in the list.

Answer 8

Pari/GP, 164 bytes

Exponential time. Am I proud of myself? No.

c(v)=if(#v>1,(sum(i=2,#v,(v[1][1]<v[i][2])&&(v[1][2]>v[i][1]))+c(v[^1])),0)
p(v)=vector(2^#v-1,i,vecextract(v,i))
m(v)=vecmax(vector(2^#v-1,i,#p(v)[i]*!c(p(v)[i])))

Try it online!

Answer 9

JavaScript (Node.js), 52 bytes

g=(a,e,m)=>a.map(([S,E])=>m=S<e|E>m?m:E)|m&&g(a,m)+1

Try it online!

Greedy join meetings that ends earliest.

Answer 10

Retina 0.8.2, 56 bytes

\d+
$*
O^$`1*,(1+)
$1
^
¶
+m`^(1*)(¶.*\1,(1+))
¶$3$2
\G¶

Try it online! Link includes test cases. Takes ;-delimited meetings. Explanation:

\d+
$*

Convert to unary.

O^$`1*,(1+)
$1

Sort by descending meeting end.

^
¶

Insert a marker for the latest meeting end so far.

+m`^(1*)(¶.*\1,(1*))
¶$3$2

Repeatedly match the meeting with the earliest end whose start is not before the latest meeting end so far, update the latest meeting end, and keep track of the number of meetings.

\G¶

Convert the number of meetings to decimal.

Answer 11

Python 2, 145, 143, 142 bytes

Saved 2 bytes thanks to Wasif pointing out that I didn't need to assign the lambda function to a variable.

lambda t:max(all(min(e,y)<=max(s,x)for(x,y),(s,e)in k(p,2))*len(p)for r in range(len(t))for p in k(t,r))
from itertools import*
k=combinations

Try it online!

Brute force approach. The program uses list comprehension to iterate through the powerset of the meetings.

Answer 12

R, 85 bytes

f=function(m)`if`((s=sum(m|1))<3,s|1,max(1+f(m[,m[1,]>=m[2]|m[2,]<=m[1]]),f(m[,-1])))

Try it online!

Input is matrix with start times in row 1 and end times in row 2.

How?

how_many_meetings=
f=function(m){                          # f = recursive function, m = input matrix  
 if((s=sum(m|1))<3)return(s|1)          # if there's only one or zero investors in the matrix, return that number,
 else{                                  # otherwise
   return(max(                          # return the max of
     1+f(m[,m[1,]>=m[2]|m[2,]<=m[1]]),  # 1 (the first investor in the matrix) + recursive call with 
                                        # all investors in the matrix that don't overlap with him/her,
     f(m[,-1]))                         # or just a recursive call without the first investor in the matrix
   )
 }
}