\(N\) 個の部署をそれぞれグループ \(A,B\) に割り当てる方法は \(2^N\) 通り（\(A,B\) の入れ替えを除けば \(2^{N-1}\) 通り）あります。
それぞれの場合について各グループに属する人数は \(O(N)\) の計算量で求めることができます。
よって、愚直にすべての場合について「同時に昼休みをとる最大人数」を計算し、その最小値を求めるのにかかる計算量は \(O(N\cdot 2^N)\) となります。
今回の \(N\leq 20\) の制約の下でこれは十分に高速です。
\(N\) 個の部署をそれぞれグループ \(A,B\) に割り当てる方法は bit 全探索などによって全列挙することができます。
よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

#define N 20
#define INF (int)2e+9

int main() {
	int n,k,s,ss=0,ans=INF;
	int a[N];

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		ss+=a[i];
	}	
	for(int i=0;i<(1<<n);i++){
		k=i,s=0;
		for(int j=0;j<n;j++){
			if(k&(1<<j))s+=a[j];
		}
		ans=min(ans,max(s,ss-s));
	}
	cout<<ans<<endl;
	return 0;
}