Prolog (SWI), 91 bytes

N+X+L:-length(S,L),append(S,X),\+ (member(Y,S),\+ (select(_,Y,G),sort(G,H),\+length(H,N))).

Try it online!

Explanation

This program defines a predicate that takes three arguments: N, the number; X, the list of numbers; and L, the number of elements in a partition of X into slender lists. If L is not bound, then it is unified first with the minimum possible number of elements in a partition of X into slender lists.

To obtain the correct output the predicate employs a brute force approach. It tries all the possible partitions of X, working from the partitions with fewest elements up, until it finds a partition where all the lists are slender. To step through all possible partitions we can use a handy bit of Prolog nondeterminism: if neither argument of length(S,L) is bound, then L is set to 0 and S to [], and as we backtrack over length(S,L), L is incremented and S is set to be a list of length L containing unbound elements. Since the append/2 predicate states that appending the elements of its first argument produce its second argument, append(S,X) binds the unbound elements of S to lists that partition X.

To check that all lists in S are slender, we assert that for all members Y of S, we can remove one element of Y to make the number of distinct numbers in the resulting list G not equal to N. We use sort/2 to find the distinct numbers in G since the sorted list it produces does not contain duplicates. To perform the for all, we use the fact that \$\forall x. (P(x) \to Q(x))\$ is logically equivalent to \$\lnot \exists x. (P(x) \land \lnot P(y))\$, since the Prolog interpreter automatically handles determining existence.

J, 39 35 34 33 bytes

1#@}.(]#~[:*/1<i.@[+/\@:="{])^:a:

Try it online!

• Create an equals table between 0 1...n and the input
• Scan sum each row
• Where is that greater than 1?
• "and" all rows (this marks the point where all items have a count of at least 2)
• Filter the original input with that mask
• Keep repeating this until a fixed point (this list vanishes)
• Return the number of iterations taken, minus one.

Haskell, 92 bytes

f n=length.foldr(\x z->last$([x]:z):[(x:a):b|a:b<-[z],or[sum[1|y<-x:a,i==y]<2|i<-[1..n]]])[]

Attempt This Online!

Ruby, 69 bytes

->n,a,*b{a[0]?a.count{|i|b<<i;(1..n).all?{b.count(_1)>1}&&b=[i]}+1:0}

Attempt This Online!

Nekomata, 11 bytes

J$RᵒĈᵐṁƶaş#

Attempt This Online!

J$RᵒĈᵐṁƶaş#
J               Find a partition of the list
 $R             Range [1, ..., n]
   ᵒ            For each number in the range and each part in the partition
    Ĉ             Count the occurrences of the number in the part
     ᵐṁ         Find the minimum count for each part
       ƶ        Check that the minimum count is at most 1
        aş      Find the shortest possible solution
          #     Take the length

If there are more than one shortest partition, it will return the same length multiple times. You can use the -1 flag to return only the first one.

Python3, 239 bytes

def f(n,l):
 q,t=[([],l)],0
 for a,L in q:
  if[]==L:t=a if not t or len(a)<len(t)else t;continue
  q+=[(a+[L[:i]],L[i:])for i in range(1,len(L)+1)if any(L[:i].count(j)<2 for j in range(1,n+1))and(not t or len(a)+1<=len(t))]
 return len(t)

Try it online!

Perl 5 -plF,, 78 bytes

@b=@a=(0)x<>;$\+=!!@F;map{$a[--$_]++;if(all{$_>1}@a){++$\;@a=@b;$a[$_]++}}@F}{

Try it online!

Charcoal, 32 bytes

Ｆη«⊞υι¿⬤…·¹θ›№υκ¹«→≔⟦ι⟧υ»»Ｉ⁺ⅈ¬¬υ

Try it online! Link is to verbose version of code. Explanation: Assumes the greedy algorithm works (it does for all of the test cases).

Ｆη«

Loop over the input list.

⊞υι

Add the next integer to the current partition.

¿⬤…·¹θ›№υκ¹

If that means that it's no longer slender, then...

«→≔⟦ι⟧υ»

... increment the partition count and use this term as the first in a new partition.

»Ｉ⁺ⅈ¬¬υ

Output the number of previous partitions plus one for the current partition unless it is empty.

The edge case for an empty input list costs 3 bytes. Taking 1-indexed input also costs 3 bytes. Otherwise, this would have sufficed for 26 bytes:

→Ｆη«⊞υι¿⬤θ›№υκ¹«→≔⟦ι⟧υ»»Ｉⅈ

Attempt This Online! Link is to verbose version of code.

05AB1E, 15 bytes

.œé.ΔεIL¢ß!}P}g

Inputs in the order \$list,n\$.

Try it online or verify all test cases.

Explanation:

.œ          # Get all partitions of the first (implicit) input-list
  é         # Sort it by length from shortest to longest
   .Δ       # The find the first (aka shortest) that's truthy for:
     ε      #  Map over each part of the current partition:
      IL    #   Push a list in the range [1, input-integer n]
        ¢   #   Get the count of each of these values in the part
         ß  #   Pop and leave the minimum count
          ! #   Factorial to change 0 to 1, while keeping 1 as is
     }P     #  After the map: check if all are truthy by taking the product
    }g      # After the find_first: pop and push the length of this shortest valid
            # partition
            # (which is output implicitly as result)

JavaScript (Node.js), 59 bytes

f=(n,a)=>a+a?1+f(n,a.filter(b=t=>!(n-=2==(b[t]=-~b[t])))):0

Try it online!

JavaScript (ES6), 66 bytes

Expects (n)(array).

n=>a=>a.map(r=o=q=g=v=>(q-=(o[v]=-~o[v])==2)?-~r:r=g(o=[v],q=n))|r

Try it online!

Jelly, 11 bytes

ŒbċⱮṂ!ɗ€€ṂL

A dyadic Link that accepts the list of integers on the left and the upper bound on the right and yields the minimal number of parts.

Try it online!

How?

ŒbċⱮṂ!ɗ€€ṂL - Link: list of integers A; integer N
Œb          - partitons of {A} (given [], yields [[]])
      ɗ€€   - for each part of each partition:
  ċⱮ        -   map count across {[1..N]}
    Ṃ       -   minimum
     !      -   factorial (Note: 0! = 1)
         Ṃ  - minimum
          L - length