Intervals

Sort by end when you're choosing intervals to keep, like activity selection, LC 435 and LC 452. The earliest end leaves the most room. Sort by start when you're combining or sweeping, like merge, insert, meeting rooms and free time. Overlapping intervals then sit next to each other.

Shortest-first can block two others. Take [1,5], [4,7], [6,10]. The shortest is [4,7] (length 3), and it overlaps both of the others, so you keep only 1. Earliest-end keeps [1,5] and [6,10], which is 2. Earliest-start fails too: [1,10], [2,3], [4,5].

It depends on the problem, so read it carefully. Merge Intervals (LC 56) treats [1,4] and [4,5] as overlapping. Non-overlapping Intervals (LC 435) treats [1,2] and [2,3] as fine together. Meeting rooms treat [5,10] and [10,15] as able to share a room. Balloons (LC 452) are closed, so one arrow at x = 2 bursts both [1,2] and [2,3]. One < vs <= decides it.

They ask opposite questions. Merge asks "is there a gap?": a new group starts only when the start is strictly after the end, so touching [1,4] and [4,5] merge. LC 435 asks "is there a clash?": a clash only when the start is strictly before the last end, so touching [1,2] and [2,3] are fine. Dhyan do: decide the touching rule first, then the sign writes itself.

An int[] is an object. merged.get(...) hands you a reference to the same array that sits inside the list, not a copy. So last[1] = 7 edits the array the list already holds. Nothing to put back. That's also why we add new int[] {iv[0], iv[1]}: a fresh copy, so stretching a group never edits the caller's input row.

It only tells Java the type you want back: an int[][]. The empty array is too small, so toArray creates a new one of exactly the right size and fills it. Without the argument, toArray() returns Object[], which you can't return as int[][].

Same idea, different syntax. For a List<Interval>: list.sort(Comparator.comparingInt(iv -> iv.start)). For an Interval[]: Arrays.sort(arr, Comparator.comparingInt(iv -> iv.start)). Employee Free Time hands you objects exactly like this.

Yes, and it's correct: add it, sort, merge. That's O(n log n). But the list is already sorted and disjoint, so the copy–absorb–copy walk does it in O(n) with no sort. Say the simple version first if you like, then give the O(n) one — that is what the interviewer is waiting for.

Both are O(n log n) and both are accepted. The sweep line is shorter and uses primitive arrays. The heap matches the story ("rooms with end times") and extends to follow-ups that ask which room to use. Know one well and mention the other.

The only question at each new meeting is "is some room free by now?". A room becomes free at its meeting's end. The smallest end in the heap is the room that frees up first, so one peek() answers it. Start times of running meetings don't help decide anything.

The new meeting needs only one room, so freeing one free room is enough. With if, the heap never shrinks: its size only grows when no room was free. So ends.size() at the end is the peak number of rooms. A while loop is also correct, but then the heap can shrink, and you must track max(size) yourself.

Picture a vertical line moving left to right over the number line. It only stops at events (starts and ends), in sorted order, and keeps a running state such as "how many intervals are open". Nothing changes between two events, so you skip that stretch. Sorting the events costs O(n log n); the walk is O(n).

No. It's called answering offline: all queries are known up front, so you may handle them in any order, as long as each answer goes back to its original position. That's why we sort an array of indices, not the queries themselves.

Nothing important. It's Meeting Rooms II with trains. Sort both arrays on their own and run the sweep: an arrival before the earliest unused departure needs a new platform. Splitting the pairs is fine because you only count, you never ask which train uses which platform. Ask one thing first: can a train arrive at the same minute another one leaves and use that platform?

Right here: the statement, the code runner and the judge on this page are free. The linked LintCode twins practise the same idea; their input format differs a little (Interval objects, or flattened arrays).