We are going to define an order $<$ on the set of $2016$ people, which we label as $X$ as follows, $x<y,(x,y)\in X\times X\iff$ person $x$ left the shop before $y$ even entered the shop. Clearly this order satisfies all conditions for a partial order. Going with the usual definition, a chain wrt this order is a set of people no two of which have been at the store at the same time while an antichain is a set of people all of which have been at the store at the same time. Let the length of greatest chain and antichain be $a$ and $b$ respectively, then by definition $k=\max(a,b)$. By Dilworth's Theorem the length of the greatest antichain is equal to the minimum number of chains required to cover the whole set $X$. Thus $\exists$ chains $X_i,1\leq i\leq b$ such that $\sum_{i=1}^b|X_i|=|X|=2016$. Now by definition $a$ is the length of the greatest chain, so $|X_i|\leq a\implies ab\geq 2016$. This gives $k^2\geq ab\geq 2016\implies k\geq 45$. To show that there is indeed a case where $k$ achieves the value $45$, we let the people numbered from $45i-44$ to $45i$ enter and leave the shop at same time $\forall 1\leq i\leq 44$ and let people numbered $45\cdot44+1$ to $2016$ enter the shop together at last. None of the other entry timings should have even a moment in common. Then clearly $k=45$. Thus the required greatest integer is $\lceil\sqrt{2016}\rceil=45$.

Lemma: Among any $mn+1$ closed intervals,there are either $m$ intervals that share a common point,or $n$ intervals that are pairwise disjoint. Proof: We proceed by induction on $n$.base cases are trivial.Let the intervals be $[a_1,b_1],\dots [a_{mn+1},b_{mn+1}]$ with $b_1 \leq b_2 \leq \dots \leq b_{mn+1}$. Assume that among any $m$ intervals,two of them are disjoint,so there are at most $m-1$ number of $a_i$'s that are smaller than $b_1$.Put these intervals($[a_1,b_1]$ and intervals having $a_i$ smaller than $b_1$) away.There are at least $m(n-1)+1$ other intervals and we can choose $n-1$ of them that are pairwise disjoint;so these $n-1$ intervals and $[a_1,b_1]$ are $n$ disjoint intervals and we are done. In the main problem,consider 2016 intervals $A_i=[a_i,b_i],i=1,2,\dots 2016$ such that $A_i$ is the period of time that customer $i$ is in the store.By lemma,if we write $2016=mn+1$ there are at least $min(m,n)$ customers that satisfy the condition,so the maximum of $k$ is achieved by letting $m=n$ which is $\lceil{\sqrt{2015}}\rceil=45$. To show that this bound is optimal,we can easily make the equality case using the algorithm in the proof of the lemma.

basically the same as above

Let $n$ be the number of customers, which is $2016$. Let $I_i = [a_i, b_i]$ be the time interval when customer $i$ is in the store. We want to find the largest integer $k$ such that there exist $k$ customers who are either all present at the same time or no two of them are present at the same time. By Mirsky's theorem (a consequence of Dilworth's Theorem), if we have a poset of size $n$, then the size of the largest antichain is equal to the minimum number of chains needed to cover the poset. Define a partial order on the intervals $I_i$ by $I_i \le I_j$ if $b_i \le a_j$, i.e., interval $I_i$ ends before interval $I_j$ begins. A chain is a set of intervals such that any two are comparable (disjoint in this case), and an antichain is a set of intervals such that any two are incomparable (intersecting in this case). We seek the largest $k$ such that there exist $k$ intervals that form a chain or $k$ intervals that form an antichain. By Erdős-Szekeres theorem, if we have a sequence of $n$ distinct numbers, there is an increasing subsequence of length $\lceil \sqrt{n} \rceil$ or a decreasing subsequence of length $\lceil \sqrt{n} \rceil$. In this context, we want to find the largest $k$ such that in any sequence of $n$ intervals, there exists a chain of length $k$ or an antichain of length $k$. By the generalization of Erdős-Szekeres theorem, if $n > rs$, then any sequence of $n$ distinct numbers has an increasing subsequence of length $r+1$ or a decreasing subsequence of length $s+1$. We are looking for $k$ such that $k^2 > n$. We have $n=2016$. We want $k$ such that $k^2 > 2016$. We have $44^2 = 1936$ and $45^2 = 2025$. Thus, we must have $k=45$. Therefore, there are either 45 pairwise disjoint intervals or 45 intervals that have a common intersection. So our answer is $\boxed{45}$