FastPrep
Problem · Intervals

Majority Labels over Audio Intervals

Learn this problem
● HardNooks logoNooksFULLTIMEPHONE SCREEN

Problem statement

You are given half-open audio intervals intervals[i] = [start, end) and a parallel array labels. Interval i contributes one active vote for labels[i] throughout its covered time.

Partition all covered audio at input endpoints. For every resulting covered segment, choose the label with the greatest number of active votes. Break equal vote counts by the lexicographically smaller label.

Omit uncovered gaps. Merge adjacent covered result segments exactly when they have the same chosen label. Return the result in start order as rows [start, end, label], with numeric endpoints serialized as decimal strings.

Function

majorityAudioIntervals(intervals: int[][], labels: String[]) → List<List<String>>

Examples

Example 1

intervals = [[0,5],[2,7],[4,6]]labels = ["alice","bob","alice"]return = [["0","6","alice"],["6","7","bob"]]

alice wins from 0 through 6, including ties by lexicographic order. Only bob remains active from 6 to 7.

Example 2

intervals = [[0,3],[1,4],[2,5],[4,6]]labels = ["b","a","a","b"]return = [["0","1","b"],["1","5","a"],["5","6","b"]]

At time 1, a ties b and wins lexicographically. Adjacent segments won by a merge through time 5.

Constraints

  • 1 <= intervals.length == labels.length <= 10^5
  • 0 <= intervals[i][0] < intervals[i][1] <= 10^9
  • Every label is a non-empty printable-ASCII string of length at most 30.
  • The returned rows are ordered by start time.
drafts saved locally
public List<List<String>> majorityAudioIntervals(int[][] intervals, String[] labels) {
    // Write your code here
}
intervals[[0,5],[2,7],[4,6]]
labels["alice","bob","alice"]
expected[["0","6","alice"],["6","7","bob"]]
checking account