Process Sequence

There is a process sequence that contains the start and end of each process.

There is a query sequence asking how many processes are running at a certain point in time.

Please return the query result of the query sequence.

The start point counts as having a process running, the end point does not.

Example 1:

Input: logs = [(1, 1234), (2, 1234)], queries = [2]Output: [2]

Example 2:

Input: logs = [(1, 1234), (1, 1235)], queries = [1234]Output: [1]

My Solutions：

题意是给定一系列进程运行的时间的开始和结束点，题目保证时长大于0。给定一系列询问，问某个时间点有多少进程在跑。如果一个进程在那个时间点开始，则计入。

brute force的做法是对queries里的每个元素，遍历logs，记录每个元素在哪几个程序内。

优化的方法是线性扫描时间。先将进程的所有开始点、结束点、询问点的时间点都做成一个pair，然后按时间排序。

如果时间相同，则开始点排在最前，结束点次之，询问点再次之（注意，这样的顺序是必要的。因为开始的进程是计入的，所以要排在最前面，而结束的进程是不计入的，排在次之，这样再扫描到query的时候，计算出的在跑的进程数才是正确的）。

接着对pair进行遍历，一边遍历一边算当前有多少个进程在跑 。

Time: O((n + m) * log(n + m))，因为要对所有时间点排序，时间点的数量是n+m，n是log的数量，m是query的数量

Space: O(n + m)

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {

    class TimePoint {
        int time;
        int type;

        public TimePoint (int time, int type) {
            this.time = time;
            this.type = type;
        }
    }
    /**
     * @param logs: Sequence of processes
     * @param queries: Sequence of queries
     * @return: Return the number of processes
     */
    public List<Integer> numberOfProcesses(List<Interval> logs, List<Integer> queries) {
        List<TimePoint> list = new ArrayList<>();

        // 将所有时间点做成一个新的object，加入list
        for (Interval log : logs) {
            list.add(new TimePoint(log.start, 0)); // start记做0，这样最小
            list.add(new TimePoint(log.end, 1));
        }
        for (int query : queries) list.add(new TimePoint(query, 2)); // 询问点记做2，这样最大

        // 对list里的元素排序
        list.sort((t1, t2) -> {
            if (t1.time == t2.time) return Integer.compare(t1.type, t2.type);
            else return Integer.compare(t1.time, t2.time);
        });

        int count = 0;
        // map用来储存对每个询问点，有多少个进程在同时进行
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < list.size(); i++) {
            TimePoint t = list.get(i);
            if (t.type == 0) count++;
            else if (t.type == 1) count--;
            
            if (t.type == 2) map.put(t.time, count);
        }

        List<Integer> res = new ArrayList<>();
        for (int q : queries) res.add(map.get(q));
        return res;
    }
}