There are $2016$ costumers who entered a shop on a particular day. Every customer entered the shop exactly once. (i.e. the customer entered the shop, stayed there for some time and then left the shop without returning back.)
Find the maximal $k$ such that the following holds:
There are $k$ customers such that either all of them were in the shop at a specic time instance or no two of them were both in the shop at any time instance.
1. **Define the problem and constraints:**
   We need to find the maximal \( k \) such that there are \( k \) customers who either were all in the shop at the same time or no two of them were in the shop at the same time. There are 2016 customers in total.

2. **Assume the existence of \(\ell\) customers:**
   Suppose there exist \(\ell\) customers who were all in the shop at the same time, but there do not exist \(\ell+1\) customers with this property.

3. **Order the customers:**
   Order the customers in the sequence they exit the shop: \( C_1, C_2, \dots, C_{2016} \), where \( C_1 \) is the first to exit.

4. **Analyze the sequence:**
   Since \( C_1 \) cannot be in the shop simultaneously with all \( C_2, C_3, \dots, C_{\ell+1} \), some of them, say \( C_{i_2} \) (where \( i_2 \leq \ell+1 \)), must have entered the shop after \( C_1 \) exited. We apply the same argument to \( C_{i_2} \) and so on, constructing a sequence \( C_1 = C_{i_1}, C_{i_2}, C_{i_3}, \dots \) with \( i_{j+1} - i_j \leq \ell \) such that no two customers in this sequence were in the shop at the same time.

5. **Calculate the number of such customers:**
   The number of such customers is at least \( \left\lceil \frac{2016}{\ell} \right\rceil \).

6. **Formulate the inequality:**
   This means that any \( k \) in question satisfies:
   \[
   k \geq k_0 := \min_{1 \leq \ell \leq 2016} \max \left\{ \ell, \left\lceil \frac{2016}{\ell} \right\rceil \right\}
   \]

7. **Determine \( k_0 \):**
   To find \( k_0 \), we need to evaluate the expression \( \min_{1 \leq \ell \leq 2016} \max \left\{ \ell, \left\lceil \frac{2016}{\ell} \right\rceil \right\} \).

8. **Approximate \( k_0 \):**
   Since \( k_0 \) is around \( \sqrt{2016} \), we can approximate:
   \[
   \sqrt{2016} \approx 44.9
   \]
   We need to check the values around this approximation.

9. **Check specific values:**
   - For \(\ell = 44\):
     \[
     \max \left\{ 44, \left\lceil \frac{2016}{44} \right\rceil \right\} = \max \left\{ 44, 46 \right\} = 46
     \]
   - For \(\ell = 45\):
     \[
     \max \left\{ 45, \left\lceil \frac{2016}{45} \right\rceil \right\} = \max \left\{ 45, 45 \right\} = 45
     \]
   - For \(\ell = 46\):
     \[
     \max \left\{ 46, \left\lceil \frac{2016}{46} \right\rceil \right\} = \max \left\{ 46, 44 \right\} = 46
     \]

10. **Conclude the value of \( k_0 \):**
    The minimum value of the maximums is 45, so \( k_0 = 45 \).

The final answer is \( \boxed{45} \).