UVA 1079 A Careful Approach (UVALive 6321, World Finals >> 2009 - Stockholm)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int n, st[10], ed[10], jump, mn, mx, arr[10];

bool isPossible(int val)
{
    int last = st[arr[0]];
    for(int i=1;i<n;i++)
    {
        if(last+val>ed[arr[i]]) return false;
        else if(last+val<st[arr[i]]) last=st[arr[i]];
        else last=last+val;
    }
return true;
}

int bs(int lo, int hi)
{
    int mid;
    while(lo<hi)
    {
        mid = (hi+lo)>>1;
        if(isPossible(mid)) lo=mid+1;
        else hi=mid;
        //cout<<hi<<" "<<lo<<endl;
    }
return lo-1;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1;
    string s;
    char ch;
    while(cin>>n && n)
    {
        mn=1e9, mn=0;
        for(int i=0;i<n;i++)
        {
            cin>>st[i]>>ed[i];
            st[i]*=60*60;
            mn=min(mn, st[i]);
            ed[i]*=60*60;
            mx=max(mx, ed[i]);
        }
        for(int i=0;i<n;i++) arr[i]=i;
        int ans = 0;
        do{
            ans = max(ans, bs(mn, mx));
        }while(next_permutation(arr, arr+n));
        //int ans = bs(mn, mx);
        if(ans%60 > 30) ans=ans/60*60+60;
        else ans = ans/60*60;
        cout<< "Case "<<kk++<<": "<<ans/3600<<":"<<setfill('0')<<setw(2)<<ans%3600/60<<"\n";
    }
return 0;
}