15
\$\begingroup\$

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 , so the shortest solution in each language wins.

\$\endgroup\$
11
  • 2
    \$\begingroup\$ May I assume all time are non negative? \$\endgroup\$ – tsh Apr 27 at 4:22
  • 2
    \$\begingroup\$ Is the input guaranteed to be nonempty? \$\endgroup\$ – att Apr 27 at 6:29
  • 3
    \$\begingroup\$ @tsh according to the 4th test case (1,2),(2,3) are not overlapping \$\endgroup\$ – EliteDaMyth Apr 27 at 7:56
  • 4
    \$\begingroup\$ It would be interesting to consider the variant where each investor had a potentially different investment amount to offer. \$\endgroup\$ – Greg Martin Apr 28 at 3:13
  • 3
    \$\begingroup\$ Redwolf Programs suggested that when I posted the challenge in Sandbox. I didn't want to do that for this challenge (since it drastically changes the algorithm) but I am working on a new "sequel" challenge where each investor offers a different amount of money. \$\endgroup\$ – knosmos Apr 28 at 3:15

12 Answers 12

15
+100
\$\begingroup\$

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!

\$\endgroup\$
9
  • 2
    \$\begingroup\$ Oh, not only does your name have one less character than his but so does this answer!!! +1 Congrats! :D \$\endgroup\$ – Noodle9 Apr 27 at 12:36
  • \$\begingroup\$ Nicely golfed! The question isn't yet eligible for a bounty, but I'll start one when it is. \$\endgroup\$ – xnor Apr 27 at 20:00
  • \$\begingroup\$ To whet the appetite can you explain some code written? Why python2, not 3? \$\endgroup\$ – Timo Apr 28 at 15:37
  • 1
    \$\begingroup\$ @Timo I've added some more explanation text, if anything is unclear feel free to ask. The code would work for Python 3 and Python 2, and since a lot of times Python 2 turns out shorter, xnor and I chose to use it here. \$\endgroup\$ – ovs Apr 28 at 16:12
  • 1
    \$\begingroup\$ I'm not entirely sure, but It seems like this works for 52 bytes. \$\endgroup\$ – dingledooper Apr 29 at 8:59
12
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ ouch... My submission is horrible. lol \$\endgroup\$ – qwatry Apr 27 at 14:39
7
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Ah, this is a dyadic Link accepting a list of starts on the left and ends on the right? I saw the Ç/€ in the footer and thought you'd need to count the / in the Link. I'm not quite sure how Ç actually manages to call the Link as a dyad here but ç/ works too (as it should). \$\endgroup\$ – Jonathan Allan Apr 27 at 17:39
  • \$\begingroup\$ @JonathanAllan yes, I think that's an acceptable input format as it is similar to the Mathematica input format. \$\endgroup\$ – rak1507 Apr 28 at 0:19
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 22 bytes

W⌊ΦEθ⮌ꬋ⊟κ∨⌈υ⁰⊞υ⊟ιILυ

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

Eθ⮌κ

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.

W⌊

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

⊞υ⊟ι

Push that earliest ending time to the predefined empty list.

ILυ

Output the number of meetings in the list.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 143 bytes \$\endgroup\$ – Wasif Apr 27 at 5:35
  • \$\begingroup\$ Thx! I'll have to read more about what the consensus is for using lambdas. I mostly just know that they are an alternative to printing. \$\endgroup\$ – qwatry Apr 27 at 5:38
1
\$\begingroup\$

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
   )
 }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.