首页 > 代码库 > find-right-interval

find-right-interval

https://leetcode.com/problems/find-right-interval/

Java里面TreeMap或者TreeSet有类似C++的lower_bound或者upper_bound的函数:floor(取出不大于xx的)和ceiling(取出不小于xx的)

package com.company;

import java.util.*;

class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
}

class Solution {
    public int[] findRightInterval(Interval[] intervals) {
        TreeMap<Integer, Integer> tmp = new TreeMap();
        for (int i=0; i<intervals.length; i++) {
            tmp.put(intervals[i].start, i);
        }

        int[] ret = new int[intervals.length];
        for (int i=0; i<intervals.length; i++) {
            Map.Entry<Integer, Integer> item =  tmp.ceilingEntry(intervals[i].end);
            if (item != null) {
                ret[i] = item.getValue();
            }
            else {
                ret[i] = -1;
            }
        }
        return ret;
    }
}

public class Main {

    public static void main(String[] args) throws InterruptedException {

        System.out.println("Hello!");
        Solution solution = new Solution();

        Interval[] intervals = new Interval[3];
        intervals[0] = new Interval(3, 4);
        intervals[1] = new Interval(2, 3);
        intervals[2] = new Interval(1, 2);
        int[] ret = solution.findRightInterval(intervals );
        System.out.printf("Get ret: %d\n", ret.length);
        for (int i=0; i<ret.length; i++) {
            System.out.printf("%d,", ret[i]);
        }
        System.out.println();

    }
}

 

find-right-interval