USACO 1.2 - Milking Cows

USACO 1.2 – Milking Cows | Jack Neus
Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).
Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):

NPUT FORMAT

Line 1:	The single integer
Lines 2..N+1:	Two non-negative integers less than 1000000, the starting and ending time in seconds after 0500

SAMPLE INPUT (file milk2.in)

3
300 1000
700 1200
1500 2100

OUTPUT FORMAT

A single line with two integers that represent the longest continuous time of milking and the longest idle time.

SAMPLE OUTPUT (file milk2.out)

900 300

X.
https://gist.github.com/stphung/917012

    int numIntervals = sc.nextInt();

    Interval[] intervals = new Interval[numIntervals];

    for (int i = 0; i < numIntervals; i++) {

      intervals[i] = new Interval(sc.nextInt(), sc.nextInt());

    }

    Arrays.sort(intervals, new Comparator<Interval>() {

      @Override

      public int compare(Interval o1, Interval o2) {

        return o1.getLow() - o2.getLow();

      }

    });

    // Single pass scan

    int low = intervals[0].getLow();

    int high = intervals[0].getHigh();

    int maxInterval = high - low;

    int maxGap = 0;

    for (int i = 1; i < intervals.length; i++) {

      Interval a = intervals[i];

      if (a.getLow() <= high) {

        high = Math.max(a.getHigh(), high);

      } else {

        maxInterval = Math.max(maxInterval, high - low);

        maxGap = Math.max(maxGap, a.getLow() - high);

        low = a.getLow();

        high = a.getHigh();

      }

    }

https://blog.csdn.net/tsing1996/article/details/72598525
题意概述：
    第一行输入一个整数N，表示有N个工作区间，接下依次输入每个区间的开始和结束时间，求从这里面最早的    一个  开始时间到最晚的结束时间这个时间区间内的最长连续工作区间和最长连续不工作区间。
解题思路：
    数据区间只在10^6范围内，且都是线性操作，所以直接用数组来模拟区间状态，但这个时候需要注意，比如   两个  工作区间分别为（100，200）,（201，300），这两个区间其实不是连续的，因此数组元素需要表示的应该   是从这个元素下标的时刻开始，到这个下标+1的时刻这一单位区间内是否处于工作的状态。因此在输入了一个区  间的开始结束时间后，要做的是把数组下标从开始时间到结束时间-1这一范围内的值都标记为工作状态.
题解代码：

http://mangogao.com/read/51.html

struct Milk

{

    int begin;

    int end;

    bool operator<(const Milk &a) const

    {

        return begin < a.begin;

    }

};

int main()

{

    ifstream fin("milk2.in");

    ofstream fout("milk2.out");

    int n;

    int left,right,ans0(0),ans1(0);

    Milk t[5000];

    fin >> n;

    for (int i = 0; i < n; ++i) fin >> t[i].begin >> t[i].end;

    sort(t,t+n);

    left = t[0].begin;

    right = t[0].end;

    for (int i = 0; i < n; ++i)

    {

        if (t[i+1].begin <= right)

        {

            right = max(right, t[i+1].end);

            ans1 = max(ans1, right-left);

        }

        else

        {

            ans1 = max(ans1, right-left);

            ans0 = max(ans0, t[i+1].begin-right);

            left = t[i+1].begin;

            right = t[i+1].end;

        }

    }

    fout << ans1 << " " << ans0 << endl;

    return 0;

}

http://jaykaychoi.tistory.com/16

X. http://code.antonio081014.com/2012/09/usaco-milking-cows.html

    public void solve() throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("milk2.in"));
        BufferedWriter out = new BufferedWriter(new FileWriter("milk2.out"));
        int N = Integer.parseInt(br.readLine());
        count = new int[1000001];
        startTime = 1000000;
        endTime = 0;
        for (int i = 0; i < N; i++) {
            String[] strs = br.readLine().split("\\s");
            int start = Integer.parseInt(strs[0]);
            int end = Integer.parseInt(strs[1]);
            startTime = Math.min(start, startTime);
            endTime = Math.max(end, endTime);
            for (int k = start; k < end; k++)
                count[k]++;
        }
        int maxTime1 = 0;
        int maxTime2 = 0;
        int tmp1 = 0;
        int tmp2 = 0;
        for (int i = startTime; i < endTime; i++) {
            if (count[i] > 0) {
                tmp1++;
                tmp2 = 0;
            }
            else {
                tmp2++;
                tmp1 = 0;
            }

            maxTime1 = Math.max(maxTime1, tmp1);
            maxTime2 = Math.max(maxTime2, tmp2);
        }
        out.write("" + maxTime1 + " " + maxTime2 + "\n");
        out.close();
    }

http://blog.tomtung.com/2007/02/usaco-milking-cows/
http://acm.sdibt.edu.cn/blog/?p=1454
http://jackneus.com/programming-archives/milking-cows/

https://computerworld.mushiyo.cf/2012/01/usacosection-12-milking-cows.html
https://www.waitig.com/usaco-section-1-2-milking-cow枚举.html

我本题的解法类似于此……虽然感觉这题的区间为1000 000没准有点太大了不可以这么玩，-_-||，但是运气好的是AC了。

bool period [MAX]; int main(int argc, char **argv) { int n,i,j; int start,finish; int was = -1,no = -1; //记录题解 int minStart = 1000002; //最初开始时间 int maxFinish = 0; //最后结束时间 ofstream fout ("milk2.out"); ifstream fin ("milk2.in"); cin >> n; for(i = 0; i<MAX; i++) { period[i] = false; } for(j = 0; j<n; j++) { cin >> start >> finish; if(start < minStart) minStart = start; if(finish > maxFinish) maxFinish = finish; for(i = start; i < finish; i++) period[i] = true; } for(i = minStart; i <= maxFinish; i++) { j = i; while(period[i] == true && i <= maxFinish) i ++; //至少有一个农民的时间 if(i-j > was) was = i-j; } for(i = minStart; i <= maxFinish; i++) { j = i; while(period[i] == false && i < maxFinish) i ++; //没有人的时间 if(i-j > no) no = i-j; } cout << was << " " << no << endl; return 0; }

Read full article from USACO 1.2 – Milking Cows | Jack Neus