guava multimap that uses TreeMap not HashMap?

Here's how you can create that beast:

Multimap<Integer,Integer> multimap = Multimaps.newListMultimap(
    Maps.<Integer, Collection<Integer>>newTreeMap(),
    new Supplier<List<Integer>>() {
        public List<Integer> get() {
            return Lists.newArrayList();
        }
    });

Guava has a TreeMultimap that stores both keys and values in sorted order. However, this uses a TreeSet for the values rather than a List so it may not quite be what you want here. In that case, Guava allows you to create a Multimap that works any way you want using one of the Multimaps.new*Multimap methods, such as Multimaps.newListMultimap. To make one that works like you describe, you'd just write this:

Map<Integer, Collection<Integer>> map = Maps.newTreeMap();
ListMultimap<Integer, Integer> m = Multimaps.newListMultimap(map,
    new Supplier<List<Integer>>() {
      public List<Integer> get() {
        return Lists.newArrayList(); // assuming you want to use ArrayList
      }
    });