java solution milk the cow
import java.util.*;
import java.io.*;
/*
ID: coconut
LANG: JAVA
TASK: milk2
*/
public class milk2 {
static farmer[] farmers;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(new File("milk2.in"));
farmers = new farmer[sc.nextInt()];
for (int i = 0; i < farmers.length; i++){
int temp = sc.nextInt();
int temp2 = sc.nextInt();
farmers[i] = new farmer(temp, temp2);
}
sc.close();
//
int longestMilk = longestMilk();
int longestNoMilk = longestNoMilk();
//
PrintWriter out = new PrintWriter(new File("milk2.out"));
out.print(longestMilk + " ");
out.println(longestNoMilk + "");
out.close();
}
static int longestMilk() {
mergeSort(farmers);
int[] allInterval = new int[farmers.length];
int lastMAX = -1;
int lastIndex = 0;
for(int i = 0;i < farmers.length; i++) {
if(lastMAX >= farmers[i].start) {
if( farmers[i].end > lastMAX){
allInterval[lastIndex] += farmers[i].end - lastMAX;
lastMAX = farmers[i].end;
}
} else {
//create a new interval
allInterval[i] = farmers[i].end - farmers[i].start;
lastMAX = farmers[i].end;
lastIndex = i;
}
}
lastMAX = -1;
for(int i : allInterval){
if(i > lastMAX)
lastMAX = i;
}
return lastMAX;
}
static int longestNoMilk() {
int[] aMI = new int[farmers.length * 2];
Arrays.fill(aMI, -1);
int point = 0;
for(farmer i : farmers){
boolean newIn = true;
for(int j = 0; j < point; j+=2){
if(aMI[j] == i.start){
if(aMI[j+1] < i.end)
aMI[j+1] = i.end;
newIn = false;
break;
} else if (i.start > aMI[j] && i.start < aMI[j+1]) {
if(i.end > aMI[j+1])
aMI[j+1] = i.end;
newIn = false;
break;
} else if (i.start < aMI[j] && i.end > aMI[j]){
if(i.end > aMI[j+1])
aMI[j+1] = i.end;
newIn = false;
break;
}
}
if (newIn){
aMI[point++] = i.start;
aMI[point++] = i.end;
}
}
//point -> smol
point = -1;
int biggestNoCow = 0;
for(int i = 1; i < aMI.length; i++){
if(point == -1)
point = aMI[i];
else {
int temp = Math.max(0, aMI[i] - point);
if(temp >biggestNoCow)
biggestNoCow = temp;
point = -1;
}
}
return biggestNoCow;
}
static void mergeSort(farmer[] list){
if(list.length > 1) {
farmer[] firstHalf = new farmer[list.length/2];
farmer[] secondHalf = new farmer[list.length - firstHalf.length];
System.arraycopy(list, 0, firstHalf, 0, firstHalf.length);
System.arraycopy(list, firstHalf.length, secondHalf,0 , secondHalf.length);
mergeSort(firstHalf);
mergeSort(secondHalf);
merge0(firstHalf, secondHalf, list);
}
}
static void merge0(farmer[] f, farmer[] s , farmer[] source ) {
int c1 = 0,c2=0,c3=0;
while(c1 < f.length && c2 < s.length) {
if (f[c1].start < s[c2].start) {
source[c3] = f[c1];
c1++;
} else {
source[c3] = s[c2];
c2++;
}
c3++;
}
while (c1 < f.length) {
source[c3] = f[c1];
c1++;
c3++;
}
while (c2 < s.length) {
source[c3] = s[c2];
c2++;
c3++;
}
}
}
class farmer{
public int start = 0;
public int end = 0;
public farmer(int start, int end){
this.start = start;
this.end = end;
}
}